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

----- Original Message ----- 
From: "Geoffrey S. Knauth" <geoff at knauth.org>
To: "Jos Koot" <jos.koot at telefonica.net>
Sent: Saturday, January 05, 2008 1:05 AM
Subject: Re: Problem with recursion? (was [plt-scheme] Re: Novice needs 
helpwriting function )


>I like your solution!

Thanks.
Earlier I said that Fibonacci would be to difficult for novices, but that 
may depend on how the problem is presented. See below.
Jos

; Compute i-th number of fib sequence starting with m and n.
; The first number of the sequence has index i=0.
; A fib sequence is an infinite sequence determined by:
; (fib 0 m n) = m
; (fib i m n) = (fib (- i 1) n (+ m n)) if i>0
; With this definition a novice easily comes up with

(define (fib i m n)
 (if (zero? i) m
  (fib (sub1 i) n (+ m n))))

; I think the generalization to (fib i m n) from (fib i 1 1)
; simplifies the problem too.

; List of first k fib numbers starting with m and n.
; Somewhat more difficult.
(define (first-fibs k m n)
 (if (zero? k) ()
  (cons m (first-fibs (sub1 k) n (+ m n)))))

#| A novice easily runs into trouble if the definition is presented as:
(fib 0) = m
(fib 1) = n
(fib i) = (+ (fib (- i 2)) (fib (- i 1))) if i>1
Mathematically this is a correct definition, of course,
but a novice may have trouble finding the loop invariant:
(fib i m n) = (fib (sub1 i) n (+ m n)) if i>0
Finding this loop invariant is a mathematical problem
rather than one of programming. |#

>
> On Jan 4, 2008, at 11:00, Jos Koot 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
>
>