On Wed, Jan 23, 2008 at 09:58:20PM -0800, [EMAIL PROTECTED] wrote:
And tail recursion allows us to nest our recursion as insanely as we want
knowing that compiler/interpreter will convert it under the hood to
a for loop for us!?!??
No, tail recursion (as defined in Scheme) _requires_ the compiler to
implement it in a memory bounded way.
I tried this in Python....
def f(x):
print x,
f(x)
It didn't go on forever but bombed with a "maximum recursion depth exceeded"
message.
Python doesn't optimize tail recursion.
Try the same example in Scheme, it'll print until you stop it, never
consuming more memory.
If all the smart kids know about tail recursion then how come the Python
interpreter couldn't/didn't use tail recursion to prevent my infinite loop from
bombing?
Python has many loop constructs so tail recursion optimization isn't
considered important.
Since tail recursion is the _only_ way to specify loops in scheme, the
compiler is required to implement it iteratively. Most scheme compilers
will generate a simple looping construct.
The basic idea is that when the compiler detects a tail-recursive call,
instead of pushing a new stack frame, it replaces it's stack frame with the
one of the call. For the easy case of a function calling itself, it can
optimize even further and keep things in registers. Suddenly, the
generated code looks just like a loop.
Dave
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
