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

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

Robby Findler wrote:
> On Jan 4, 2008 12:41 PM, Yavuz Arkun <yarkun at> 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.


Posted on the users mailing list.