Hi there.
I'm trying to define a function to compute Fibonacci numbers up to ten
thou. This is what I have so far:
(defun fibonacci ()
(dotimes (n 10000)
(cond ((< n 2) print n)
(t fibonacci (+ (1- n) (- 2 n))))))
but when I do this, the REPL returns:
NIL.
Could someone point me to where I am going wrong here, please? Am I
even right to use recursion?
TIA
Jeff
Jeff Rollin wrote:
> Hi there.
>
> I'm trying to define a function to compute Fibonacci numbers up to ten
> thou. This is what I have so far:
>
> (defun fibonacci ()
> (dotimes (n 10000)
> (cond ((< n 2) print n)
> (t fibonacci (+ (1- n) (- 2 n))))))
>
> but when I do this, the REPL returns:
>
> NIL.
>
> Could someone point me to where I am going wrong here, please? Am I
> even right to use recursion?
Let's start with the recursive definition of Fibonacci number:
f(0) = 1
f(1) = 1
f(n) = f(n-1) + f(n-2), for n > 1, n an integer.
Translate this directly into a recursive function, with no DOTIMES
(which is an iteration construct, incidentally), and show me what you've
written here. It should be four lines of code, max, with proper
indenting and spacing and all.
Incidentally, don't try running that code on n = 10000, because it will
be very, very slow ;-P After you've gotten the code to work for some
small numbers (n <= 10), come back and we'll talk about how to optimize it.
mfh
Jeff Rollin wrote:
> Hi there.
>
> I'm trying to define a function to compute Fibonacci numbers up to ten
> thou. This is what I have so far:
>
> (defun fibonacci ()
> (dotimes (n 10000)
> (cond ((< n 2) print n)
> (t fibonacci (+ (1- n) (- 2 n))))))
>
> but when I do this, the REPL returns:
>
> NIL.
>
> Could someone point me to where I am going wrong here, please? Am I
> even right to use recursion?
Let's start with the recursive definition of Fibonacci number:
f(0) = 1
f(1) = 1
f(n) = f(n-1) + f(n-2), for n > 1, n an integer.
Translate this directly into a recursive function, with no DOTIMES
(which is an iteration construct, incidentally), and show me what you've
written here. It should be four lines of code, max, with proper
indenting and spacing and all.
Incidentally, don't try running that code on n = 10000, because it will
be very, very slow ;-P After you've gotten the code to work for some
small numbers (n <= 10), come back and we'll talk about how to optimize it.
mfh
Jeff Rollin wrote:
> Hi there.
>
> I'm trying to define a function to compute Fibonacci numbers up to ten
> thou. This is what I have so far:
>
> (defun fibonacci ()
> (dotimes (n 10000)
> (cond ((< n 2) print n)
> (t fibonacci (+ (1- n) (- 2 n))))))
>
> but when I do this, the REPL returns:
>
> NIL.
>
> Could someone point me to where I am going wrong here, please? Am I
> even right to use recursion?
Let's start with the recursive definition of Fibonacci number:
f(0) = 1
f(1) = 1
f(n) = f(n-1) + f(n-2), for n > 1, n an integer.
Translate this directly into a recursive function, with no DOTIMES
(which is an iteration construct, incidentally), and show me what you've
written here. It should be four lines of code, max, with proper
indenting and spacing and all.
Incidentally, don't try running that code on n = 10000, because it will
be very, very slow ;-P After you've gotten the code to work for some
small numbers (n <= 10), come back and we'll talk about how to optimize it.
mfh
Mark Hoemmen wrote:
> Jeff Rollin wrote:
>
>> Hi there.
>>
>> I'm trying to define a function to compute Fibonacci numbers up to ten
>> thou. This is what I have so far:
>>
>> (defun fibonacci ()
>> (dotimes (n 10000)
>> (cond ((< n 2) print n)
>> (t fibonacci (+ (1- n) (- 2 n))))))
>>
>> but when I do this, the REPL returns:
>>
>> NIL.
>>
>> Could someone point me to where I am going wrong here, please? Am I
>> even right to use recursion?
>
>
> Let's start with the recursive definition of Fibonacci number:
No, let's start with dotimes returning nil unless you tell it otherwise:
(let ((y 0))
(dotimes (x 10 y) (incf y 10)) -> 45
:)
kt
Ken Tilton wrote:
>
>
> Mark Hoemmen wrote:
>> Jeff Rollin wrote:
>>
>>> Hi there.
>>>
>>> I'm trying to define a function to compute Fibonacci numbers up to ten
>>> thou. This is what I have so far:
>>>
>>> (defun fibonacci ()
>>> (dotimes (n 10000)
>>> (cond ((< n 2) print n)
>>> (t fibonacci (+ (1- n) (- 2 n))))))
>>>
>>> but when I do this, the REPL returns:
>>>
>>> NIL.
>>>
>>> Could someone point me to where I am going wrong here, please? Am I
>>> even right to use recursion?
>>
>>
>> Let's start with the recursive definition of Fibonacci number:
>
> No, let's start with dotimes returning nil unless you tell it otherwise:
>
> (let ((y 0))
> (dotimes (x 10 y) (incf y 10)) -> 45
>
> :)
>
> kt
Actually, I started by inserting a (print) statement in the last part! That
was why the function was returning NIL. ;-)
Thanks for the reply.
Jeff
Jeff Rollin wrote:
> (defun fibonacci ()
This line says your fibonacci function doesn't take any arguments.
> (t fibonacci (+ (1- n) (- 2 n))))))
Several comments:
1. If you want to call fibonacci, it has to be the first thing
in a pair of parentheses. The name without parentheses is
a variable named fibonacci, not your function.
2. What are you trying to do with the + form?
As it's written, you're adding the numbers n-1 and n-2.
To get the fibonacci function of n, you need to add
the fibonacci functions of n-1 and n-2, not the numbers
themselves.
3. To pass a number to fibonacci, you have to
define your function as taking an argument n.
> (dotimes (n 10000)
How do you want to calculate all those different
fibonacci values? If you want to calculate them
separately, then your dotimes loop should be outside
your fibonacci function, in another function that calls
fibonacci several times. If you want to calculate them
together with dotimes, you need to print each fib value
and save it in a variable before calculating the next one.
That will not be a recursive solution.
And as Ken said, dotimes doesn't return a value unless
you specify it after the upper limit.
--
Dan
www.prairienet.org/~dsb/
On Tue, 22 May 2007 19:11:12 +0200, Jeff Rollin
<··············@googlemail.com> wrote:
> Hi there.
>
> I'm trying to define a function to compute Fibonacci numbers up to ten
> thou. This is what I have so far:
>
> (defun fibonacci ()
> (dotimes (n 10000)
> (cond ((< n 2) print n)
> (t fibonacci (+ (1- n) (- 2 n))))))
>
> but when I do this, the REPL returns:
>
> NIL.
>
> Could someone point me to where I am going wrong here, please? Am I
> even right to use recursion?
>
> TIA
>
> Jeff
>
Well there is a lot wrong here.
A Fibonacci sequence is:
fib(n) = fib(n-1) + fib(n-2)
n 0 1 2 3 4 5 6
fib 1 1 2 3 5 8 13
For one thing you have to start at the beginning.
The loop is nonsense.
This is a useful first approximation:
(defun fib (n &optional (cur 1) (n-2 1) (n-1 1))
(cond
((< n 2) 1)
((= cur n) n-1)
(t (fib n (1+ cur) n-1 (+ n-2 n-1)))))
As you see it remembers 3 values.
cur is the current counter
n-2 is the value from the iteration two calls ago
n-1 is the value from 1 call ago
since we only start at 2 these are defaulted to 1 so fib(2)=1+1=2
The second condition exits with the accumulated value which is stored in
n-1
The default branch uses a recursive call to fib. it:
1. increments cur
2. stores n-1 in the n-2 position
3. calculates current fib value and stores it in n-1 position
The good news is that this function is tail-recursive so the compiler
can optimize the call away and make a loop for you.
(The ANSI standard does not guaranteed this but most compilers do this if
optimisation debug < speed or debug < 3 which is usually default)
The bad news is that this is terribly inefficient for computing all values
up to 10000.
It is much better to remember the result of the last computations.
(defun fibseq (n &optional (cur 1) (seq (list 1 1)))
(cond
((< n 1) 1)
((< n 2) (list 1 1))
((= cur n) (nreverse seq))
(t (fibseq n (1+ cur) (push (+ (second seq) (first seq)) seq)))))
CL-USER 5 > (fibseq 6)
(1 1 2 3 5 8 13)
Kinda like the last one but this one returns a list of the Fibonacci
numbers.
Since you use push you get the numbers pushed on the list in the reverse
order.
Therefore before we exit we in-place reverse the list.
Also we can now read the two last values from the seq list.
Be aware that this list gets very big for 10000.
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
Hi John
John Thingstad wrote:
> On Tue, 22 May 2007 19:11:12 +0200, Jeff Rollin
> <··············@googlemail.com> wrote:
>
>
>
> Well there is a lot wrong here.
> A Fibonacci sequence is:
>
> fib(n) = fib(n-1) + fib(n-2)
>
> n 0 1 2 3 4 5 6
> fib 1 1 2 3 5 8 13
>
> For one thing you have to start at the beginning.
> The loop is nonsense.
> This is a useful first approximation:
>
> (defun fib (n &optional (cur 1) (n-2 1) (n-1 1))
> (cond
> ((< n 2) 1)
> ((= cur n) n-1)
> (t (fib n (1+ cur) n-1 (+ n-2 n-1)))))
>
> As you see it remembers 3 values.
So the (defun...) line initializes cur, n-2, and n-1, allowing you to
specify them if you wish?
> cur is the current counter
> n-2 is the value from the iteration two calls ago
> n-1 is the value from 1 call ago
> since we only start at 2 these are defaulted to 1 so fib(2)=1+1=2
> The second condition exits with the accumulated value which is stored in
> n-1
> The default branch uses a recursive call to fib. it:
> 1. increments cur
> 2. stores n-1 in the n-2 position
Not sure I understand why you write "n-1" and not "(n-1)" here.
> 3. calculates current fib value and stores it in n-1 position
>
> The good news is that this function is tail-recursive so the compiler
> can optimize the call away and make a loop for you.
> (The ANSI standard does not guaranteed this but most compilers do this if
> optimisation debug < speed or debug < 3 which is usually default)
>
> The bad news is that this is terribly inefficient for computing all values
> up to 10000.
That's fair enough. I'm just trying to get a handle on the process here.
Optimization can come later. You can probably tell this code isn't going
anywhere near a production app any time soon ;-).
> It is much better to remember the result of the last computations.
>
> (defun fibseq (n &optional (cur 1) (seq (list 1 1)))
> (cond
> ((< n 1) 1)
> ((< n 2) (list 1 1))
> ((= cur n) (nreverse seq))
> (t (fibseq n (1+ cur) (push (+ (second seq) (first seq)) seq)))))
>
> CL-USER 5 > (fibseq 6)
> (1 1 2 3 5 8 13)
>
> Kinda like the last one but this one returns a list of the Fibonacci
> numbers.
> Since you use push you get the numbers pushed on the list in the reverse
> order.
> Therefore before we exit we in-place reverse the list.
> Also we can now read the two last values from the seq list.
>
> Be aware that this list gets very big for 10000.
>
See above, re: optimization.
Thankyou very much, very helpful.
Jeff.
On Tue, 22 May 2007 22:36:06 +0200, Jeff Rollin <··············@gmail.com>
wrote:
>
> Not sure I understand why you write "n-1" and not "(n-1)" here.
>
n-1 and n-2 are variable names.
>
> That's fair enough. I'm just trying to get a handle on the process here.
> Optimization can come later. You can probably tell this code isn't going
> anywhere near a production app any time soon ;-).
>
right! You might want to hide the variables and make a local recusive
function.
>> (defun fibseq (n &optional (cur 1) (seq (list 1 1)))
>> (cond
>> ((< n 1) 1)
>> ((< n 2) (list 1 1))
>> ((= cur n) (nreverse seq))
>> (t (fibseq n (1+ cur) (push (+ (second seq) (first seq)) seq)))))
>>
(defun fibseq (n)
(check-type n (integer 0 *))
(cond
((< n 1) 1)
((< n 2) (list 1 1))
(t
(labels ((rec (cur seq)
(if (= cur n)
(nreverse seq)
(rec (1+ cur) (push (+ (second seq) (first seq)) seq)))))
(rec 1 (list 1 1))))))
The check-type raises a exception if given a anything but a natural number.
labels defines a local recurive function rec.
Note that there are no optional variables to fibseq.
Also the checks for values 0 and 1 for n need be performed only once.
n is seen from the scope of fibseq so you dont have to pass it as a
parameter.
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
Jeff Rollin <··············@googlemail.com> writes:
> Hi there.
>
> I'm trying to define a function to compute Fibonacci numbers up to ten
> thou. This is what I have so far:
>
> (defun fibonacci ()
> (dotimes (n 10000)
> (cond ((< n 2) print n)
> (t fibonacci (+ (1- n) (- 2 n))))))
>
> but when I do this, the REPL returns:
>
> NIL.
>
> Could someone point me to where I am going wrong here, please? Am I
> even right to use recursion?
>
Ummm. I think you have quite a few problems. To start with, you seem to have a
mix of iteration and recursion - you need to go back to the drawing board and
re-think what you are trying to do. Some things to look at
1. How are the arguments passed in your recursive call i.e. what are they bound
to? Where is n getting its value from?
2. Do you actually get a fibonacci sequence when you substitute 1, 2, 3, 4, 5
for n?
Start by lookinig again at the definition of a fibonacci sequence. Work out an
algorithm in pseudo code and run through it with different starting values.
Once you have the pseudo code for the algorithm, get a basic lisp text and look
at how to define a function, iteration and recursion. have another go and come
back with the next list of questions. Don't try to get what you have working,
your function definition and the algorithm it is trying ti implement is
completely wrong. Better to start fresh.
Tim
--
tcross (at) rapttech dot com dot au
In the last episode, on Wednesday 23 May 2007 04:43, Tim X wrote:
> Jeff Rollin <··············@googlemail.com> writes:
>
>> Hi there.
>>
>> I'm trying to define a function to compute Fibonacci numbers up to ten
>> thou. This is what I have so far:
>>
>> (defun fibonacci ()
>> (dotimes (n 10000)
>> (cond ((< n 2) print n)
>> (t fibonacci (+ (1- n) (- 2 n))))))
>>
>> but when I do this, the REPL returns:
>>
>> NIL.
>>
>> Could someone point me to where I am going wrong here, please? Am I
>> even right to use recursion?
>>
>
> Ummm. I think you have quite a few problems. To start with, you seem to
> have a mix of iteration and recursion - you need to go back to the drawing
> board and re-think what you are trying to do. Some things to look at
>
> 1. How are the arguments passed in your recursive call i.e. what are they
> bound to? Where is n getting its value from?
> 2. Do you actually get a fibonacci sequence when you substitute 1, 2, 3,
> 4, 5 for n?
>
> Start by lookinig again at the definition of a fibonacci sequence. Work
> out an algorithm in pseudo code and run through it with different starting
> values. Once you have the pseudo code for the algorithm, get a basic lisp
> text and look at how to define a function, iteration and recursion. have
> another go and come back with the next list of questions. Don't try to get
> what you have working, your function definition and the algorithm it is
> trying ti implement is completely wrong. Better to start fresh.
>
> Tim
>
That seems like a nice summary of everything that was wrong with the
original code (!) so I'll reply to the discussion here IIM.
First of all, apologies for the late reply. Second of all, thanks for all
the great responses. I'll forgo posting code I've written myself as the
smorgasbord you've all kindly donated is more than enough to show me where
I've gone wrong, as well as other approaches.
Thanks again, great newsgroup.
Jeff