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

Marco Morazan wrote:
>> 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
>
>   
The iterative model I had in mind was something more like:

int fib(N) {
    int i, a[2] = {1, 1};
    for(i= 3; i <= N; i++) a[i % 2] += a[(i + 1) % 2];
    return a[N % 2];
}

You are right that there are at least 4 explicit variables in iterative 
versions, since you need to keep track of the limit, current iteration 
and 2 members. To balance, there are no implicit values that need to be 
passed around.

The number of explicit variables in the recursive version is deceptive. 
When I am trying to understand a program, I put myself in the place of 
the computer and work through the program in my mind. For the iterative 
version, everything I need to remember are explicitly named. For 
recursive algorithms, I need to keep track of the implicit variables as 
well, such as how deep I am into the recursion, and what the 
intermediate values are, because I will need them on my way back.

Personally, I can manage 1 or 2 levels mentally, and if I use pen and 
paper maybe a few more. After that, I need to take a leap of faith, and 
inductively conclude that if it works for the simplest case, and for the 
one after that, it should work for all cases.

In other words, neither the conciseness of the program text, nor the 
elegance of the expressed ideas necessarily means "easy to understand", 
unless you are prepared to take the leap.

I can do that, because I know recursion works as a general concept. It 
may be more difficult if you are new to the idea. Even more so, when you 
realize that the 'elegant' method can have rather inelegant space and/or 
time characteristics. Then you start to feel like you must be missing 
something and become frustrated.

Therefore, recursion (like any other method) should be illustrated using 
examples that can be best solved with recursion.

Yavuz