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

From: Jos Koot (jos.koot at telefonica.net)
Date: Fri Jan 4 11:00:12 EST 2008

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
> 



Posted on the users mailing list.