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

>*
*>* BTW, I first learned about the Fibonacci series in high school, and we
*>* were told they are generated by "start with 1, 1, and then add the last
*>* 2 together to get the next one...", e.g. iteratively. For me the
*>* recursive definition is contrived, and I saw it for the first time in
*>* intro programming books. I guess this shows that prior teaching of
*>* iterative style kills some neurons forever.
*>*
*
;;; fib: number -> number
(define (fib n)
;;; if n is 1 or 2 the nth fib. number is 1
;;; if n > 2
;;; (fib (- n 1)) is the (n-1)th fib. number
;;; (fib (- n 2)) is the (n-2)th fib. number
;;; (+ (fib (- n 1)) (fib (- n 2)) is the nth fib. number
(cond [(or (= n 1) (= n 2)) 1]
[else (+ (fib (- n 1)) (fib (- n 2)))]))
What is contrived about this? It precisely follows the definition you outlined.
Now, the iterative version:
if (n <= 2)
{return(1);}
else
f1 = 1;
f2 = 1;
curr = 2;
k = 3;
while (k < n)
{
k = k + 1;
f1 = f2;
f2 = curr;
curr = f1 + f2;
}
return(curr);
That looks contrived to me. All of the sudden we have 5 variables
(i.e. n, k, f1, f2, and curr) instead of just one (i.e. n) like in the
recursive version. Furthermore, I have to carefully place my
statements. If the order is changed it will not work.
Cheers,
Marco