The iterative version's magic can be explained by Tail Recursion Elimination. Python creator Guido's post on why he left it out of Python might be an interesting read: http://neopythonic.blogspot.in/2009/04/tail-recursion-elimin...
Comments like "Third, I don't believe in recursion as the basis of all programming." and recursion "is just a nice theoretical approach to fundamental mathematics (turtles all the way down), not a day-to-day tool." Makes me wonder how long he was exposed to Scheme. For me, programming in Scheme is a wonderful experience, way more pleasant that in Python.
In Scheme is really clear what is an efficient or inefficient piece of code. Rather in Python, where I found myself going back and forward trying to figuring out what is happening behind the scenes to see if I can do it in a more efficient way.
Don't get me wrong, I will take a slow Python against something faster like Java any day. But I have Scheme in the top of my preferences and that hasn't changed since 17 years ago when I was introduced to Scheme for first time.
Fortunately, thanks to Clojure being a Lisp, you can add it yourself:
But I will say it seems really weird to me to refuse tail-call recursion flat out. People even do it in C as an optimization (http://llvm.org/docs/Passes.html#tailcallelim-tail-call-elim...).
function r(x)
if x == 1 then
return 1
else
return r(x-1)
end
end
r(100000000)
[spc]saltmine:/tmp>lua t.lua
^Clua: t.lua:6: interrupted!
stack traceback:
t.lua:3: in function 'r'
t.lua:6: in function <t.lua:2>
(tail call): ?
(tail call): ?
(tail call): ?
(tail call): ?
(tail call): ?
(tail call): ?
(tail call): ?
(tail call): ?
...
(tail call): ?
(tail call): ?
(tail call): ?
(tail call): ?
(tail call): ?
(tail call): ?
(tail call): ?
(tail call): ?
t.lua:10: in main chunk
[C]: ?
[spc]saltmine:/tmp>
function start()
i = getinput()
if i == A then
return state_A()
elseif i == B then
return state_B()
else
return state_error()
end
end
function state_A()
return state_B()
end
function state_B()
i = getinput()
if i == MORE then
return state_A()
else
return DONE
end
end
function state_error()
return ERROR;
end
I can't speak to every optimizing interpreter or compiler, but in the few that I've used, TCO doesn't do anything to code that doesn't have tail calls, so lots of the code has "accurate" stack traces.
And when it does perturb the stack trace, it does so in a very obvious way, it abbreviates the tail calls. Such stack traces no longer have a 1:1 mapping with the function "calls," but are still quite informative for debugging purposes. Not as informative as they would be if you turn TCO off just to debug that code, but informative enough that I rarely had to turn it off.
If you're application is complex enough that inspection won't reveal the source of the bug, then stack traces are almost strictly less useful than logging.
A good backtrace for a crash or exception can tell me the entire call stack. Logging at that granularity (i.e. every time a function is called) is not a good idea.
This whole debug dump issue could be avoided by saving a copy of the initial entry frame for debugging and the current frame with elipses shown between them when TCE was in effect.
So yeah, you could make the case that it's not "an accurate stack trace", because it isn't. But, you don't want that. You want TCO. Trust me on this.
Preemptive strike for the bikeshedder crowd in the back :) : if you think you can deduce some useful fact from a recursive function that's stacktraced, like for example where in the loop the function gave an error, then you're wrong. Go learn to use a debugger.
That's not correct. It's not TRO, TCO. So as it's normally understood any call in tail position would be eliminated.
In Python today, this program:
def foo():
bar()
def bar():
baz()
def baz():
raise Exception('OH NOES')
foo()
Traceback (most recent call last):
File "raise.py", line 10, in <module>
foo()
File "raise.py", line 2, in foo
bar()
File "raise.py", line 5, in bar
baz()
File "raise.py", line 8, in baz
raise Exception('OH NOES')
Exception: OH NOES
Traceback (most recent call last):
File "raise.py", line 8, in baz
raise Exception('OH NOES')
Exception: OH NOES
TCO is a fine feature in languages where its deeply engrained and part of its natural idioms. Bolting it on twenty years later doesn't seem that helpful to me.
Although TCO is often essential and I have written large blocks of code that depend on it, I have also long advocated better heuristics for when to turn it off so as not to impede debugging. The compromise taken, for example, by some Common Lisp implementations, where calls from one top-level function to another are not tail-optimized but local calls (calls to functions defined with LABELS or FLET) are, in my experience works very well most of the time.
But for experienced programmers, I agree global TCO doesn't quite rise to the level of a major impediment, though I have found it an annoyance at times. It particularly bugs me when the code I'm debugging is not recursive, so I'm not getting any benefit from TCO in this particular case.
For novice programmers, however, I think it could be a serious barrier. I think van Rossum was right not to have Python do it by default. But I think he should also have provided a way to define a set of mutually-tail-recursive functions.
I have long experience with Franz Allegro CL, which does TCO only on local calls. I think it's the best of both worlds: debugging usually isn't interfered with, and on those occasions where I really want to write a set of mutually-tail-recursive routines, it gives me a way to do that. I have certainly also used CL implementations that do global TCO -- I think that's all of the major open-source ones -- and they're certainly usable, but I prefer the Allegro compromise.
Luckily, in the lisp and scheme families (possibly also other image based PLs), it's easy to mix compiled (and optimized) and interpreted code. Whenever i run into a bug such that i need the debugger to fix it, I always replace the compiled function with an interpreted version first, making it much easier to debug. What you get in the stacktraces is the same as you read on the screen.
In most lisp implementations, this maneuver can be performed completely on line, you don't have to restart the program or recompile anything but the function under inspection itself. When the runtime signals an exception or fault, just tell lisp to interpret the suspect function. Then move up the stack to the function that called the suspect, and restart that stack frame et voilá, bob is your uncle.
(a) there are techniques to deal with that, and (b) where's the accurate stack trace from a state-maintaining while loop, or a trampoline?
In any production code I would rather prefer performance than debugging. Isn't that the point why C/C++ programmers have debug and release configurations? to turn off debugging features on a production code?
Losing stack frames for recursive functions is not so bad. The real violence that TCO does is to non-recursive tail calls, which form the majority of tail calls, at least in non-functional languages.
In any case, it's possible to have both, if the compiler outputs some (optional) extra debug information. For example, gcc has options that let you reconstruct a 'virtual' stack trace in gdb even for inlined functions.
As someone said in the comments below Guido's post, providing meaningful stack traces in presence of TCO is possible, it just requires a little more bookkeeping on language part.