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

From: Jos Koot (jos.koot at
Date: Fri Jan 4 12:18:06 EST 2008

----- Original Message ----- 
From: "Marco Morazan" <morazanm at>
To: "Jos Koot" <jos.koot at>
Cc: "Robby Findler" <robby at>; "Yavuz Arkun" 
<yarkun at>; <plt-scheme at>
Sent: Friday, January 04, 2008 5:56 PM
Subject: Re: Problem with recursion? (was [plt-scheme] Re: Novice needs 
helpwriting function )

>> The procedure
>>  (define (fib n)
>>     (cond [(or (= n 1) (= n 2)) 1]
>>          [else (+ (fib (- n 1))  (fib (- n 2)))]))
>> is a  horrible example of recursion considering the number of recursive
>> calls needed and the number of duplicated computations. That's why I 
>> could
>> not withstand posting my example. :)
> Well, "horrible" means different things in different contexts. My
> posting was addressing the claim that the recursive definition is
> "contrived." No claim was made that this is the best or most efficient
> way of computing fib numbers.

Ok, it was certainly not my intention to offend you. If you felt offended, 
accept my appologies please

> Issues of efficiency need to be studied,
> but not while getting your first exposure to recursion.

That is correct. Nevertheless it seems not right to me to present the 
example to novices. They could be tempted to acquire a habbit of thoughtless 
application of recursion. Starting with lists and (later) trees and showing 
the connection between data structure and program structure, seems a better 
approach to me (as in HtDP and The Little Schemer) Then after a feeling of 
the flow of evaluation, more complicated examples can come in. Just MHO.

> The naive definition above is elegant, not contrived, and something
> inexperienced students can understand. I would certainly not use
> streams and fib numbers to teach recursion to those who are seeing it
> for the first time.

Agreed. I already made a remark to the same extent in my earlier posting.

> Marco

Posted on the users mailing list.