Re: Tail recursion

"jjb" <Alexey.Mikhailov@gmail.com> wrote in message
news:06-11-018@comp.compilers...
> Hello!
>
> Recently I read about "tail recursion" (in SICP) - ability of
> programming language realization to convert linear recursive proccess
> to linear iterative proccess. So I tried to find formal algorithm of
> this transformation for any function written using functional paradigm
> but I failed. May be someone can help me?
>
> Some trivial example here is calculating factorial.
>
> Linear recursive:
> fact n = if (n < 3) then n else (n * fact(n-1))


        First of all, note that it's always possible to convert any
program written in a "recursive style" to a program written in an
"iterative style", in the Turing-Complete sense. But some programs are
easier to convert than others. Tail recursions happen to be one of
those easy cases.


http://en.wikipedia.org/wiki/Tail_recursion
<quote>


When a function is called, the computer must "remember" the place it
was called from, the return address, so that it can return to that
location with the result once the call is complete. Typically, this
information is saved on the stack, a simple list of return locations
in order of the times that the call locations they describe were
reached. Sometimes, the last thing that a function does after
completing all other operations is to simply call a function, possibly
itself, and return its result. But in this case, there is no need to
remember the place we are calling from — instead, we can leave the
stack alone, and the newly called function will return its result
directly to the original caller. Converting a call to a branch or jump
in such a case is called a tail call optimization. Note that the tail
call doesn't have to literally appear after all other statements in
the source code; it is only important that its result be immediately
returned, since the calling function will never get a chance to do
anything after the call if the optimization is performed.


</quote>


        Note that in the function you wrote, the function call is not the
last thing that occurs: you make the function call, and then multiply
the result by n. The Wikipedia article gives an example of rewriting
the factorial function so that it becomes tail-recursive (by adding a
second argument).


        - Oliver

Return to the comp.compilers page.
Search the comp.compilers archives again.