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

----- Original Message ----- 
From: "Marco Morazan" <morazanm at gmail.com>
To: "Jos Koot" <jos.koot at telefonica.net>
Cc: "Geoffrey S. Knauth" <geoff at knauth.org>; <plt-scheme at list.cs.brown.edu>
Sent: Saturday, January 05, 2008 4:53 PM
Subject: Re: Problem with recursion? (was [plt-scheme] Re: Novice needs 
helpwriting function )


> >
>> ; 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))))
>>
>
> Essentially, you have now changed the contract on the fib function
> from fib: num -> num to num num num -> num if you leave the problem at
> this point. This tail-recursive version is efficient and only requires
> one more step to meet the original contract by making the above
> function an auxilary function. :-)

Right

> The point is that any user of the fib function is likely to want to
> only be interested in (and only want to be bothered with) inputing the
> i for the ith fib number of their interest. There is no need for them
> to be bothered with the m and n.

Essentially I changed the exercise such as to make a function that 
represents ALL Fibonacci sequences. If I remember well, Fibonacci sequences 
are not restricted to
(1 1 2 etc) or (0 1 1 2 etc)
They may start with two arbitrary numbers, I think, although
(lambda (i) (fib i 0 0))
is not very interesting, of course.
The more general exercise is much easier than the particular one. To come up 
with the generalization may be too difficult a step for a novice and rather 
is mathematics than programming, I think.

> ;;; fibonacci: num -> num
> (define (fibonacci i)
>  (fib i 0 1))

This is sequence (0 1 1 2 etc) not (1 1 2 etc)  :)

Cheers, Jos
>
> Cheers,
>
> Marco
>