what *exactly* is tail recursion?
Author Message
what *exactly* is tail recursion?

Quote:

>Can anyone give me a formal definition of what qualifies as tail
>recursion?  Informally, i tend to think of it as anything that would
>allow the compiler to substitute the bottoming out part of the
>recursion with a single GOTO to the very first call.

Yes, basically.  I find it a little easier to think about in terms
of tail *calling* rather than tail *recursion*.  So in your non-tail-
recursive example

Quote:
>  (define (notail-fact n)
>    (if (= n 0) 1
>    (* n (notail-fact (- n 1)))))

this procedure *does* make a tail call, to the * procedure.  When * is
finished, it can return its result directly to the caller of notail-fact
(which might be another invocation of notail-fact).

Once you have that idea, then tail recursion is just a tail call to
the same procedure.  But thinking in terms of tail calling also lets
you understand situations such as mutual tail recursion, in which
procedure A tail-calls B, and B tail-calls A.

FAQ person:  This should be in the FAQ!

Sat, 19 Oct 1996 07:43:10 GMT
what *exactly* is tail recursion?
: >  (define (notail-fact n)
: >    (if (= n 0) 1
: >  (* n (notail-fact (- n 1)))))

: this procedure *does* make a tail call, to the * procedure.  When * is
: finished, it can return its result directly to the caller of notail-fact
: (which might be another invocation of notail-fact).

: Once you have that idea, then tail recursion is just a tail call to
: the same procedure.  But thinking in terms of tail calling also lets
: you understand situations such as mutual tail recursion, in which
: procedure A tail-calls B, and B tail-calls A.

Well that seems to suggest that tail recursion is just a compiler
optimization technique, namely to replace the stack frame of the
caller with the stack frame of the last callee, instead of push
the new stack frame to the stack.

Am I right?
--
----------

"Ay, fashion you may call it.  Go to, go to." -- Hamlet

Sun, 20 Oct 1996 19:37:51 GMT
what *exactly* is tail recursion?

Quote:

>Well that seems to suggest that tail recursion is just a compiler
>optimization technique, namely to replace the stack frame of the
>caller with the stack frame of the last callee, instead of push
>the new stack frame to the stack.

>Am I right?

Yes, that's my understanding.  Some people would argue with your
use of the word "just," because in effect a tail-calling compiler
can turn a recursion into an iteration, thereby eliminating one
of the big fears that the Real Programmer types have about Lisp.

Sun, 20 Oct 1996 22:55:23 GMT
what *exactly* is tail recursion?

Quote:

>>Well that seems to suggest that tail recursion is just a compiler
>>optimization technique, namely to replace the stack frame of the
>>caller with the stack frame of the last callee, instead of push
>>the new stack frame to the stack.

>Yes, that's my understanding.  Some people would argue with your
>use of the word "just," because in effect a tail-calling compiler
>can turn a recursion into an iteration, thereby eliminating one
>of the big fears that the Real Programmer types have about Lisp.

A machine-independent way of looking at 'tail recursion' is as a use
of the lambda-calculus 'eta' axiom on the continuation:

Axiom eta:  (lambda (x) (foo x)) => foo

E.g., (bar 3 4 (lambda (z) (foo z))) => (bar 3 4 foo)

The logicians of the 20's and 30's were just as curious about
eta/tail-recursion as we are.  They found that 'eta' is _independent_
of the other axioms like 'alpha' (renaming) and 'beta' (in-lining).

Mon, 21 Oct 1996 05:04:55 GMT
what *exactly* is tail recursion?
A basic concept taught to Scheme programmers is the difference between a
non-tail-recursive implementation of factorial:

(define (factorial n)
(if (= n 0)
1
(* n (factorial (- n 1)))))

and a tail-recursive one:

(define (factorial n)
(define (loop n c)
(if (= n 0)
c
(loop (- n 1) (* n c))))
(loop n 1))

While the later is more efficient, in most cases, the former is easier to
understand, write, and debug. My question is: Has there been any work on
automatically converting programs from the former style to the later? If so,
are there any implementations that do so?
Thanks,
Jeff

Tue, 22 Oct 1996 23:21:05 GMT

 Page 1 of 1 [ 5 post ]

Relevant Pages