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

On Jan 4, 2008 12:41 PM, Yavuz Arkun <yarkun at gmail.com> wrote:
>
> 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];
> }

And yet your English text suggests this definition:

 fib(0)=1
 fib(1)=1
 fib(n+2) = fib(n) + fib(n+1)

which, I believe, is even executable code in some programming language
or other (not that that's particular relevant, tho).

As far as the mental model of the computer that you seem to work with
(below), I am amazed at your ability to burrow through (a couple)
abstractions. I'm remarkably bad at that, myself. But lets not forget
that the purpose of abstractions to let people build bigger and bigger
things on top of them and, to that end, it is important to make them
seamless and then rely on that. Esp. for novices.

Robby

> 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
>
> _________________________________________________
>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>