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

From: Yavuz Arkun (yarkun at gmail.com)
Date: Fri Jan 4 15:43:54 EST 2008

Robby Findler wrote:
> 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.
>>>>         
>>>       
>> 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).
>
>   
Well, my English text had the "..." which in my mind was the explicit 
loop. The mathematical version you gave makes that an implicit one. I 
believe my C version is closer to the English text's spirit because its 
formulated as an explicit iteration. What may be confusing in the C 
version is the use of % operator to translate the "last 2" into C code. 
(BTW, I am no C expert...I am sure it can be written more idiomatically.)

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

I didn't mean that I can go down 2 levels in terms of abstraction (e.g., 
Scheme code -> Scheme interpreter -> assembly operations). I mean that I 
can follow through only a few recursive calls of Fibonacci before 
forgetting where I was. My little brain hurts already.

Yavuz


Posted on the users mailing list.