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

Your remark about 'simple' is right, of course. My conclusion is that an 
example as the Fibonacci numbers (or binomials) should not be the first one. 
The Little Schemer/LISPer introduces streams very naturally in the exercises 
of Chapter 9 (out of 10) and then uses streams for a very beautiful example 
of recursion: (define P ...) (define Q ...) (No I am not going to tell what 
P and Q do, for it's an exercise :)

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. :)
Jos

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


>I think maybe you use the word "simple" in a way different from the
> way others are using it here. For you "simple" means "best, clearest
> way after you already know everything" not "best clearest way to
> present to novices".
>
> :)
>
> Robby
>
> On Jan 4, 2008 10:00 AM, Jos Koot <jos.koot at telefonica.net> wrote:
>> For me the following is the most simple recursive:
>>
>> (define (make-fib-stream n m)
>>  (cons n (lambda () (make-fib-stream m (+ n m)))))
>>
>> (define (fib n) ; return n-th fib number
>>  (if (zero? n) 1
>>   (fib-aux n (make-fib-stream 1 1))))
>>
>> (define (fib-aux n stream)
>>  (if (zero? n) (car stream)
>>   (fib-aux (sub1 n) ((cdr stream)))))
>>
>> (time (fib 300))
>> (map fib '(0 1 2 3 4 5 6 7 8 9))
>>
>> Welcome to DrScheme, version 371.3-svn26oct2007 [3m].
>> Language: Textual (MzScheme, includes R5RS) custom.
>> cpu time: 0 real time: 0 gc time: 0
>> 359579325206583560961765665172189099052367214309267232255589801
>> (1 1 2 3 5 8 13 21 34 55)
>> >
>> Jos Koot
>>
>>
>> ----- Original Message -----
>> From: "Marco Morazan" <morazanm at gmail.com>
>> To: "Yavuz Arkun" <yarkun at gmail.com>
>> Cc: <plt-scheme at list.cs.brown.edu>
>> Sent: Friday, January 04, 2008 3:52 PM
>> Subject: Re: Problem with recursion? (was [plt-scheme] Re: Novice needs
>> helpwriting function )
>>
>>
>> > >
>> >> 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
>> > _________________________________________________
>> >  For list-related administrative tasks:
>> >  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>> >
>>
>> _________________________________________________
>>   For list-related administrative tasks:
>>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>>
>