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  
 
 [ 5 post ] 

 Relevant Pages 

1. Tail recursion and complete recursion?

2. OO, lexical scope, closure, tail-recursion, continuation

3. Lisp type list, recursion and tail call optimisation

4. Tail recursion ???

5. Tail recursion

6. Thanks for the tail recursion

7. How is tail-recursion optimized in Smalltalk?

8. Any Smalltalk supporting tail recursion optimization ?

9. Tail-optimized recursion

10. tail recursion analysis

11. tail recursion -- what's a good name

12. Recognising tail recursion

 

 
Powered by phpBB® Forum Software