From: Johann Hibschman <johann@...>
Date: 2001-09-23T11:45:59+09:00
Subject: [ruby-talk:21588] Re: Math and Programming

>>>>> "Joel" == Joel Wilsson <siigron@sii.linuxsweden.nu> writes:

    Joel> Yes, overflowing the stack is the reason why recursion isn't
    Joel> always the best way to solve a problem.  Tail-recursion
    Joel> solves the problem of overflowing the stack by not
    Joel> allocating a new stack unless it has to.  If the last thing
    Joel> a function does is call itself, there is no need to keep the
    Joel> old stack - the current stack can be re-used for the new
    Joel> call.

It doesn't have to call itself.  If the last thing a function
does is call another function, it can just turn that call into a
goto, if the compiler is smart enough.

i.e.

def f(x)
  g(x+1)
end

def g(y)
  puts x
end

f(10)

can be translated into something like

<push return frame onto stack>
<jump to f's code, with argument of 10>
<jump to g's code, with argument of 11>
<puts 11>
<pop return>

rather than

<push return frame onto stack>
<jump to f's code, with argument of 10>
<push return frame onto stack>
<jump to g's code, with argument of 11>
<puts 11>
<pop return>
<pop return>

A function calling itself is just a special case of this.

--Johann