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

[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. A tail recursive version of the fact function would look
like:

(define (fact n)
  (let loop ((n n) 
             (result 1))
    (if (<= n 1)
        result
        (loop (- n 1) (* result n)))))

And this _is_ optimized by guile. The old version 

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

gives a stack overflow for (fact 889) on my system. The tail-recursive version
lets me do (fact 10000) and more. The computation takes some time then, due
to the multiplication of the bignums. To see that no stack frames are
allocated, change the * into a + and you can do a (fact 100000) in short
execution time.

Best regards, 
Dirk Herrmann