begin quoting Wade Curry as of Sat, Jan 26, 2008 at 12:20:31PM -0800: > David Brown([EMAIL PROTECTED])@Thu, Jan 24, 2008 at 11:34:00AM -0800: > > On Thu, Jan 24, 2008 at 11:13:00AM -0800, [EMAIL PROTECTED] wrote: > > >On Thu, Jan 24, 2008 at 11:06:52AM -0800, SJS wrote: > > >>Iteration is fast. > > >>Recursion is elegant. > > > > > >I like this. > > > > And, in Scheme, you get both. Even better. > > > > So, now that I understand this a _little_ better, how does scheme > compare to common lisp in regard to optimizing tail recursion? Is > tail recursion as efficient as iteration in CL?
A procedure call pushes another stack frame to the stack, so that returning from the procedure call consists of popping the current stack frame off the stack (and discarding it) and using the next one down. So normal recursion pushes a stack frame for every level of the recursion. A deep recursion will then, therefore, exhaust the stack. Tail recursion is when the very last statement is the recursive call -- all the calling procedure will do when the called procedure finishes is to immediately return. So why bother pushing a stack frame? It's not going to be used by anyone, ever*. So instead of incrementing the stack pointer, the stack frame is reinitialized (generally a no-op) and control passes to the start of the procedure again. [*] Unless you use dynamically scoped variables instead of lexically scoped variables. > My grasp of tail recursion is far from solid. I haven't been able > to go through the SICP course for lack of time. One of the earlier > posts said something about it being important to distinguish tail > recursion from other recursion. Is this something that is easy to > get wrong? What would the pitfalls be? Stack overflow. Personally, I think lispy languages are exactly the wrong language family to demonstrate tail recursion; Pascal or C work better, IMO. The *best* way is with a chalkboard machine: this box is the stack, this box is my heap, this box is my program. . . -- Perhaps an animated GIF Or maybe an ASCII diff. Stewart Stremler -- [email protected] http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
