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