10 ms·

This article really got me in the mood to play around with Racket again. Incidentally, I find it hard to square with Guido's belief that recursion isn't the ba

This article really got me in the mood to play around with Racket again. Incidentally, I find it hard to square with Guido's belief that recursion isn't the basis of all programming. Sure, Python has some powerful iterators, but my CS professors made it clear that iteration is basically just a special case of recursion. It might very well be the right decision for Python to prefer iteration, but to deny the role of recursion in computer science altogether seems misguided.

Dewie 12y ago
> , but my CS professors made it clear that iteration is basically just a special case of recursion. That seems a bit disingenuous, since iteration and general recursion are fundamentally equivalent. So you could say that "recursion is just a special case of iteration". Unless we're talking about specific iterations like iterating over a list, I guess.
- danking00 12y ago
  I feel that it is a bit disingenuous to claim they are equivalent if the solution to maintaining a call stack is to explicitly maintain a stack structure. Iterating over lists, or integers in a range is pretty straightforward. Iterating over a tree? What does that even mean? I suppose we could take "iterate" to mean a catamorphism. Under that interpretation, structural recursion and "iteration" seem pretty equivalent. Just feels like quite an extension of what "iteration" usually refers to in a language like C.
  - Dewie 12y ago
    > I feel that it is a bit disingenuous to claim they are equivalent if the solution to maintaining a call stack is to explicitly maintain a stack structure. You're funny. Equivalent in a computational sense.
    - danking00 12y ago
      But by that standard ruby is python is C is assembler. Turing-completeness is a not very interesting standard.
  - agumonkey 12y ago
    Good point. I always felt that iteration was 1-dimensional, when recursion is more fractal / N-dimensional. ps: Also, a lot of programming is often conflated into 1-D. sed, grep, awk are mostly init ; iterate{ [PRED] FN }; exit
  - rdc12 12y ago
    But with TCO it is no longer needed to maintain a stack structure, so it would probably be a better stated as a tail-call recursive function is equivalent to iteration (assuming TCO)
nostrademons 12y ago
The two of them are exactly the same thing, but in recursion you have an implicit stack that maintains the state of each iteration. In iteration, the stack is either explicit or else condensed down into a few state variables (eg. if you're just keeping a sum, you don't need to store all the intermediate partial sums). Given that Python's philosophy is "explicit is better than implicit", it doesn't surprise me that he prefers iteration to recursion.
- rpedroso 12y ago
  My issue was more about his opposition to recursion than the preference for iteration. That being said, this is one of the better explanations/arguments for why iterations are more 'Pythonic' that I've heard. Thanks!
  - Veedrac 12y ago
    Guido is not opposed to recursion per-se, just on basing programming around it. As he says, > TRE only addresses recursion that can easily be replaced by a loop and Python already has a very nice tool for that purpose. I have no doubt that he's fine with many other uses of recursion.
  - Veedrac 12y ago
    Guido is not opposed to recursion per-se, just on basing programming around it. As he says, > TRE only addresses recursion that can easily be replaced by a loop and Python already has a very nice tool for that purpose. I have no doubt that he's fine with many other uses of recursion.
  - beagle3 12y ago
    His opposition to recursion is well founded on the "principle of least surprise" that also underlies Python. Consider, e.g. def len1(list, acc=0): if not list: return acc else: return len1(list[1:],acc+1) def len2(list, acc=0): if not list: return acc else: return len2(list[1:],acc+1) + 0 First one is using only tail calls, and with proper TRE will run on any sized list. The second one will blow up the stack, despite being equivalent in almost every sense, especially in those senses (of "ease of proof") touted as the main reason to use tail recursion in the first place. And while this toy examples is easy to reason about, real world examples require more experience to understand - and Python was always intended at non CS people (and is hugely successful in that mission). Personally, I think the whole discussion is misguided. TRE should be explicit, not some kind of implicit optimization - that is, no TRE/TCO unless you explicity use e.g. a "chain" return keyword: def len3(list, acc=0): if not list: return acc else: chain len1(list[1:],acc+1) This way, a compiler could warn you about a syntax error should you rely on TRE and it is impossible or not available; Same thing could (and should) be done in scheme/lisp etc; It's easy to shoot yourself in the foot with macros and tailcalls in scheme. "chain" might not be the right keyword for this, but I haven't found a better one ("tail-return", "return-only", "continue-with" don't seem any better"; maybe reuse "pass"? e.g. "return pass len1(..)" or "pass return len1(...)"
iamcurious 12y ago
I have the same thoughts about list comprehension. The first time I read this quote I thought Guido was being ironic: "filter(P, S) is almost always written clearer as [x for x in S if P(x)]"
- zem 12y ago
  the comprehension version is actually clearer, though. consider: in filter(P, S) 1. which is the predicate and which is the list? 2. is the list filtered in place (destructively) or is a new list emitted? 3. does filter mean "select when P" or "reject when P"? both are valid readings of the english word 'filter', with common non-scitech usage actually leaning more towards 'filter out' the list comprehension has none of those ambiguities.
  - jdpage 12y ago
    The C#/LINQ syntax for this is nice for this reason. It's S.Where(P), which makes it clear that the thing on the left is the thing being filtered, and that it's taking values x where P(x) is true. One could also make the argument that it also suggests that it's a non-destructive operation, but that might just be years of familiarity with SQL semantics talking.
  - actsasbuffoon 12y ago
    To be explicit, they're clearer _in Python_ due to the prevailing style and sensibilities of the community. It's possible to adopt a different set of guidelines that would eliminate the ambiguity. For instance, in Haskell the data you're working with is always the last argument. This stems from the way currying works, which makes life much more pleasant if the predicate comes first. Ruby also makes it clear, as there's special syntax for passing an anonymous function to a function call. For your second point, pure functional languages have complete clarity in this sort of thing. In Haskell it's obvious that you're returning a new list, and you couldn't mutate the original even if you wanted to. Ruby has a convention where ambiguously-mutating function names are suffixed with "!" to indicate that this version mutates. As for your third point, I can see where you're coming from, but filter is a venerable function name. There's a version of filter in most functionally inspired languages (and a version of map, reduce, etc.) and all the ones I've seen only keep elements that match the predicate. I suppose this may be why Ruby calls it "select" instead of "filter". There's also an inverted version called "reject". All of those also have an in-place variant (select!, reject!, map!). My point is that the ambiguity is not unavoidable. These things could easily be made clearer with different conventions/language-support. Other languages do quite well with these tools, so it obviously can be done in a clear way.
cttet 12y ago
"iteration is basically just a special case of recursion" for and while loop are just special case of usage of goto, but this does not necessary means that we need to use goto.
easytiger 12y ago
> but my CS professors made it clear that iteration is basically just a special case of recursion. More realistically iteration is a practically usable form of recursion to be used in stack based environments. Why do you think you have to optimise recursion into iteration before you can do anything non trivial with it
nemoniac 12y ago
Henry G. Baker made the point well, already in 1992. "The appearance of iterators [..] appears to be inversely related to the power of the language's intrinsic control structures." http://home.pipeline.com/~hbaker1/Iterator.html http://home.pipeline.com/~hbaker1/Iterator.html

Dewie 12y ago

> , but my CS professors made it clear that iteration is basically just a special case of recursion. That seems a bit disingenuous, since iteration and general recursion are fundamentally equivalent. So you could say that "recursion is just a special case of iteration". Unless we're talking about specific iterations like iterating over a list, I guess.

danking00 12y ago
I feel that it is a bit disingenuous to claim they are equivalent if the solution to maintaining a call stack is to explicitly maintain a stack structure. Iterating over lists, or integers in a range is pretty straightforward. Iterating over a tree? What does that even mean? I suppose we could take "iterate" to mean a catamorphism. Under that interpretation, structural recursion and "iteration" seem pretty equivalent. Just feels like quite an extension of what "iteration" usually refers to in a language like C.
- Dewie 12y ago
  > I feel that it is a bit disingenuous to claim they are equivalent if the solution to maintaining a call stack is to explicitly maintain a stack structure. You're funny. Equivalent in a computational sense.
  - danking00 12y ago
    But by that standard ruby is python is C is assembler. Turing-completeness is a not very interesting standard.
- agumonkey 12y ago
  Good point. I always felt that iteration was 1-dimensional, when recursion is more fractal / N-dimensional. ps: Also, a lot of programming is often conflated into 1-D. sed, grep, awk are mostly init ; iterate{ [PRED] FN }; exit
- rdc12 12y ago
  But with TCO it is no longer needed to maintain a stack structure, so it would probably be a better stated as a tail-call recursive function is equivalent to iteration (assuming TCO)

nostrademons 12y ago

The two of them are exactly the same thing, but in recursion you have an implicit stack that maintains the state of each iteration. In iteration, the stack is either explicit or else condensed down into a few state variables (eg. if you're just keeping a sum, you don't need to store all the intermediate partial sums). Given that Python's philosophy is "explicit is better than implicit", it doesn't surprise me that he prefers iteration to recursion.

rpedroso 12y ago
My issue was more about his opposition to recursion than the preference for iteration. That being said, this is one of the better explanations/arguments for why iterations are more 'Pythonic' that I've heard. Thanks!
- Veedrac 12y ago
  Guido is not opposed to recursion per-se, just on basing programming around it. As he says, > TRE only addresses recursion that can easily be replaced by a loop and Python already has a very nice tool for that purpose. I have no doubt that he's fine with many other uses of recursion.
- Veedrac 12y ago
  Guido is not opposed to recursion per-se, just on basing programming around it. As he says, > TRE only addresses recursion that can easily be replaced by a loop and Python already has a very nice tool for that purpose. I have no doubt that he's fine with many other uses of recursion.
- beagle3 12y ago
  His opposition to recursion is well founded on the "principle of least surprise" that also underlies Python. Consider, e.g. def len1(list, acc=0): if not list: return acc else: return len1(list[1:],acc+1) def len2(list, acc=0): if not list: return acc else: return len2(list[1:],acc+1) + 0 First one is using only tail calls, and with proper TRE will run on any sized list. The second one will blow up the stack, despite being equivalent in almost every sense, especially in those senses (of "ease of proof") touted as the main reason to use tail recursion in the first place. And while this toy examples is easy to reason about, real world examples require more experience to understand - and Python was always intended at non CS people (and is hugely successful in that mission). Personally, I think the whole discussion is misguided. TRE should be explicit, not some kind of implicit optimization - that is, no TRE/TCO unless you explicity use e.g. a "chain" return keyword: def len3(list, acc=0): if not list: return acc else: chain len1(list[1:],acc+1) This way, a compiler could warn you about a syntax error should you rely on TRE and it is impossible or not available; Same thing could (and should) be done in scheme/lisp etc; It's easy to shoot yourself in the foot with macros and tailcalls in scheme. "chain" might not be the right keyword for this, but I haven't found a better one ("tail-return", "return-only", "continue-with" don't seem any better"; maybe reuse "pass"? e.g. "return pass len1(..)" or "pass return len1(...)"

iamcurious 12y ago

I have the same thoughts about list comprehension. The first time I read this quote I thought Guido was being ironic: "filter(P, S) is almost always written clearer as [x for x in S if P(x)]"

zem 12y ago
the comprehension version is actually clearer, though. consider: in filter(P, S) 1. which is the predicate and which is the list? 2. is the list filtered in place (destructively) or is a new list emitted? 3. does filter mean "select when P" or "reject when P"? both are valid readings of the english word 'filter', with common non-scitech usage actually leaning more towards 'filter out' the list comprehension has none of those ambiguities.
- jdpage 12y ago
  The C#/LINQ syntax for this is nice for this reason. It's S.Where(P), which makes it clear that the thing on the left is the thing being filtered, and that it's taking values x where P(x) is true. One could also make the argument that it also suggests that it's a non-destructive operation, but that might just be years of familiarity with SQL semantics talking.
- actsasbuffoon 12y ago
  To be explicit, they're clearer _in Python_ due to the prevailing style and sensibilities of the community. It's possible to adopt a different set of guidelines that would eliminate the ambiguity. For instance, in Haskell the data you're working with is always the last argument. This stems from the way currying works, which makes life much more pleasant if the predicate comes first. Ruby also makes it clear, as there's special syntax for passing an anonymous function to a function call. For your second point, pure functional languages have complete clarity in this sort of thing. In Haskell it's obvious that you're returning a new list, and you couldn't mutate the original even if you wanted to. Ruby has a convention where ambiguously-mutating function names are suffixed with "!" to indicate that this version mutates. As for your third point, I can see where you're coming from, but filter is a venerable function name. There's a version of filter in most functionally inspired languages (and a version of map, reduce, etc.) and all the ones I've seen only keep elements that match the predicate. I suppose this may be why Ruby calls it "select" instead of "filter". There's also an inverted version called "reject". All of those also have an in-place variant (select!, reject!, map!). My point is that the ambiguity is not unavoidable. These things could easily be made clearer with different conventions/language-support. Other languages do quite well with these tools, so it obviously can be done in a clear way.

cttet 12y ago

"iteration is basically just a special case of recursion" for and while loop are just special case of usage of goto, but this does not necessary means that we need to use goto.

easytiger 12y ago

> but my CS professors made it clear that iteration is basically just a special case of recursion. More realistically iteration is a practically usable form of recursion to be used in stack based environments. Why do you think you have to optimise recursion into iteration before you can do anything non trivial with it

nemoniac 12y ago

Henry G. Baker made the point well, already in 1992. "The appearance of iterators [..] appears to be inversely related to the power of the language's intrinsic control structures." http://home.pipeline.com/~hbaker1/Iterator.html http://home.pipeline.com/~hbaker1/Iterator.html