tail-end-recursion.scm

   1 ; tail-end-recursion.scm
   2 ; Simple examples of how to use tail-end recursion in Scheme, and how they are
   3 ; much faster than their simpler counterparts.
   4 ; Only one example so far, but I'm sure the other /prog/ members can add to it.
   5
   6 (define (fibonacci n)
   7   (define (fibonacci-acc n a b)
   8     (if (> n 0)
   9       (fibonacci-acc (- n 1) b (+ a b))
  10       a))
  11   (fibonacci-acc n 0 1))
  12
  13 (define (fibonacci-slow n)
  14   (cond ((= n 0) 0)
  15         ((= n 1) 1)
  16         (else (+ (fibonacci-slow (- n 1))
  17                  (fibonacci-slow (- n 2))))))