I gather than the author is being hyperbolic in order to emphasize his point ("is easier to reason about correctness with recursion"). But the reason recursion doesn't "suck" in python (an other languages without TCE), even with a small call stack, is that usually it is used to tackle problems with a divide-and-conquer strategy. Even if you are handling a massive amount of items, if your recursive calls splits them to handle in two or more parts until there's no more to handle, then it is very hard to deplete the call stack:<p>log2 1_000_000_000_000_000 => 49.82892142331043<p>"Recursion and iteration are equally expressive: recursion can be replaced by iteration with an explicit stack, while iteration can be replaced with tail recursion. Which approach is preferable depends on the problem under consideration and the language used." [1]<p>BTW, I sympathize with the author's thesis. I was trying to remember algorithms that are easier to reason about in their iterative form... but I can't remember any. Conversely, compare recursive vs iterative DFS [2].<p>1: <a href="http://en.wikipedia.org/wiki/Recursion_(computer_science)" rel="nofollow">http://en.wikipedia.org/wiki/Recursion_(computer_science)</a><p>2: <a href="http://en.wikipedia.org/wiki/Tree_traversal#Depth-first_2" rel="nofollow">http://en.wikipedia.org/wiki/Tree_traversal#Depth-first_2</a>
This article really got me in the mood to play around with Racket again.<p>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.<p>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.
This is also one of many reasons why people love Lua.<p>Lua does proper tail recursion automatically.<p><a href="http://www.lua.org/pil/6.3.html" rel="nofollow">http://www.lua.org/pil/6.3.html</a>
This was a great article. I've spent the last year filling in gaps in my own CS background including CL, Scheme, Racket, CISP, HtDP, etc. This is the first time I've seen good solid reasoning about Scheme using Assembly and it makes things really clear. I wish the author would have taken a little more time reasoning to the correctness of recursion using the y combinator. That's what he ended up with but it would have been helpful to break that down a bit more. Also, he mentioned that his next article in that series would have covered continuations (specifically call-with-current-continuation) and I REALLY would have enjoyed that since I find continuations a little hard to grasp.
If your goal is to reason about correctness, recursion can be a useful tool. Assembly... is not the hammer I'd bust out for that particular reasoning task.
It would've been nice if mathematical induction were indicated as the foundation of recursion. You're not assuming "it does the right thing" and then proving "it does the right thing". What you're doing is that you're proving that "it does the right thing" by showing that "it does the right thing for N" if "it does the right thing for N-1", and your terminal condition is something like "it does the right thing for 0". Thus mathematical induction takes care of both correctness and termination.
> is easier to reason about correctness<p>> my favorite programming language is x64 assembly<p>So, author is _really_ used to reading asm and also smarter than an average developer (and yours truly) or doesn't really care about being able to reason that much.<p>(But let me be clear, I'm not being sarcastic and wouldn't be surprised if he's really 10x genius.)
Great article. Fun to read about both Scheme and Assembly at the same time since I'm currently taking class on each (6.004, 6.945 @ MIT). It's great to get theory from both ends of the abstraction spectrum.
I don't get the argument about why loop invariants are any more complicated than tail calls. The link doesn't seem to clear it up (the same problem would occur with the direct translation to tail recursion).