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