From: WJ <w_a_x_man@...>
Date: 2011-04-20T13:15:31+09:00
Subject: Re: Tail Call Optimization (Tail Recursion)

Louis-Philippe wrote:

> the thing is the tail recursive one doesn't really yield the full sequence
> as it omits the 0, and so:
> 
> fib(30)          => 832040
> tail_fib(30)    => 1346269


Corrected:

;;  Gambit Scheme

(define (fib n)
  (define (%fib n a b)
    (if (= 1 n)
      b
      (%fib (- n 1) b (+ a b))))
  (%fib n 0 1))

(println "30th fibonacci number is " (fib 30))

(define bigfib 0)
(time
  (set! bigfib (fib 50000)))
(let* ((str (number->string bigfib))
       (len (string-length str)))
  (println "Result of (fib 50000) has " len " digits:")
  (println (substring str 0 9) " ... " (substring str (- len 9) len)))

  ==>

30th fibonacci number is 832040
(time (set! bigfib (fib 50000)))
    562 ms real time
    516 ms cpu time (500 user, 16 system)
    807 collections accounting for 157 ms real time (188 user, 0 system)
    119070200 bytes allocated
    no minor faults
    no major faults
Result of (fib 50000) has 10450 digits:
107777348 ... 373553125