Problem with recursion? (was [plt-scheme] Re: Novice needs helpwriting function )

From: Marco Morazan (morazanm at
Date: Sat Jan 5 10:53:11 EST 2008

> ; Compute i-th number of fib sequence starting with m and n.
> ; The first number of the sequence has index i=0.
> ; A fib sequence is an infinite sequence determined by:
> ; (fib 0 m n) = m
> ; (fib i m n) = (fib (- i 1) n (+ m n)) if i>0
> ; With this definition a novice easily comes up with
> (define (fib i m n)
>  (if (zero? i) m
>  (fib (sub1 i) n (+ m n))))

Essentially, you have now changed the contract on the fib function
from fib: num -> num to num num num -> num if you leave the problem at
this point. This tail-recursive version is efficient and only requires
one more step to meet the original contract by making the above
function an auxilary function. :-)

The point is that any user of the fib function is likely to want to
only be interested in (and only want to be bothered with) inputing the
i for the ith fib number of their interest. There is no need for them
to be bothered with the m and n.

;;; fibonacci: num -> num
(define (fibonacci i)
  (fib i 0 1))



Posted on the users mailing list.