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

 From: Marco Morazan (morazanm at gmail.com) Date: Fri Jan 4 09:52:31 EST 2008 Previous message: Problem with recursion? (was [plt-scheme] Re: Novice needs help writing function ) Next message: Problem with recursion? (was [plt-scheme] Re: Novice needs helpwriting function ) Messages sorted by: [date] [thread] [subject] [author]

```>
> 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

```

 Posted on the users mailing list. Previous message: Problem with recursion? (was [plt-scheme] Re: Novice needs help writing function ) Next message: Problem with recursion? (was [plt-scheme] Re: Novice needs helpwriting function ) Messages sorted by: [date] [thread] [subject] [author]