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
>