Problem with recursion? (was [plt-scheme] Re: Novice needs helpwriting function )
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
>