Re: Tail recursion and hobbit (was: finite state machines in guile)

[Doug Evans <devans@cygnus.com>]

   Date: Mon, 5 Oct 1998 16:23:35 +0200 (CEST)
   From: Dirk Herrmann <dirk@ida.ing.tu-bs.de>

   On Mon, 5 Oct 1998, Bernard URBAN wrote:

   > Exactly. For instance, the following is not tail call optimized:
   > 
   > (define (fact n)
   >   (if (<= n 1)
   >       1
   >       (* n fact (- n 1))))
   > 
   > even if equivalent to the original factorial. But guile's interpreter may
   > also fail to optimize this (I have no way to verify this, any hint ?).

   Guile does not optimize it. But if I am right, the call to fact is _not_ a
   tail call anyway.

Yep.

   (define (fact n)
     (if (<= n 1)
	 1
	 (* n (fact (- n 1)))))

   gives a stack overflow for (fact 889) on my system.

Another nice way to see this is with ...

guile> (trace fact)
(fact)
guile> (fact 5)
[fact 5]
|  [fact 4]
|  |  [fact 3]
|  |  |  [fact 2]
|  |  |  |  [fact 1]
|  |  |  |  1
|  |  |  2
|  |  6
|  24
120
120

And tracing a silly version to make clear the tail-recursion ...

guile>(define (fact2 n result) (if (<= n 1) result (fact2 (- n 1) (* n result)\
)))
guile> (trace fact2)
(fact2)
guile> (fact2 5 1)
[fact2 5 1]
[fact2 4 5]
[fact2 3 20]
[fact2 2 60]
[fact2 1 120]
120
120
guile>