# Re: Tail recursion

## "Oliver Wong" <owong@castortech.com>8 Nov 2006 00:19:32 -0500

From comp.compilers

Related articles
[5 earlier articles]
Re: Tail recursion Wilco.Dijkstra@arm.com (Wilco Dijkstra) (2000-08-21)
Re: Tail recursion mrs@kithrup.com (2000-08-21)
Re: Tail recursion ian0kerr@my-deja.com (2000-09-08)
Tail recursion Alexey.Mikhailov@gmail.com (jjb) (2006-11-04)
Re: Tail recursion kym@ukato.freeshell.org (russell kym horsell) (2006-11-04)
Re: Tail recursion diablovision@yahoo.com (2006-11-05)
Re: Tail recursion owong@castortech.com (Oliver Wong) (2006-11-08)
Re: Tail recursion jboehm@gmx.net (=?ISO-8859-1?Q?J=FCrgen_B=F6hm?=) (2007-02-04)
| List of all articles for this month |

 From: "Oliver Wong" Newsgroups: comp.compilers Date: 8 Nov 2006 00:19:32 -0500 Organization: Compilers Central References: 06-11-018 Keywords: analysis, optimize Posted-Date: 08 Nov 2006 00:19:32 EST

"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
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

Post a followup to this message