Computing fibonacci numbers (rank newbie)
Jeff Rollin
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
Mark Hoemmen
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
Let's start with the recursive definition of Fibonacci number:
Mark Hoemmen
Let's start with the recursive definition of Fibonacci number:
Ken Tilton
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
John Thingstad
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/
Jeff Rollin
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
John Thingstad wrote:
> On Tue, 22 May 2007 19:11:12 +0200, Jeff Rollin
> <jeffrey...@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.
John Thingstad
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.
Dan Bensen
> (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/
viper-2
> NIL.
Jeff:
You're confusing iteration with recursion. Chapters 5 and 7 of Winston
and Horn's "Lisp" (3rd edition) do a good job of explaining recursion
and iteration. As Mark pointed out, DOTIMES is an iterative construct.
If you just want to print the fibonacci numbers you can have a look at
the following code. The recursive version is not the most efficient,
but it will help you recognize the fibonacci calculation easily.
This is the iterative version:
>
(defun fib-iter (x)
(let ((one 0) (two 1) (three 1))
(dotimes (n (1+ x))
(setf one two two three three (+ one two))
(print one))))
FIB-ITER
>
(fib-iter 8)
1
1
2
3
5
8
13
21
34
NIL
This is the recursive version:
>
(defun fibber (x)
(if (or (= x 0) (= x 1))
1
(+ (fibber (- x 1))
(fibber (- x 2)))))
FIBBER
>
(defun fib-recur (x)
(cond ((zerop (1+ x)))
(t (print (fibber x)) (fib-recur (1- x)))))
FIB-RECUR
>
(fib-recur 8)
34
21
13
8
5
3
2
1
1
T
>
You will have to do lots of exercises to get the hang of both
iteration and recursion. I printed the first eight fibonacci numbers.
I don't recommend you try to do anything near 10,000 - it will take
forever ....
agt
Tim X
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
Alan Crowe
> and Horn's "Lisp" (3rd edition) do a good job of explaining recursion
> and iteration.
> You will have to do lots of exercises to get the hang of both
> iteration and recursion. I printed the first eight fibonacci numbers.
> I don't recommend you try to do anything near 10,000 - it will take
> forever ....
>
I think the original poster could usefully spend some time
at the REPL just playing and seeing stuff happen. For
example start with
CL-USER> (defun recurse (x)
(format t "~&Starting on ~A." x)
(if (zerop x)
(format t "~&The end.")
(recurse (- x 1)))
(format t "~&Finishing off ~A" x))
RECURSE
CL-USER> (recurse 3)
Starting on 3.
Starting on 2.
Starting on 1.
Starting on 0.
The end.
Finishing off 0
Finishing off 1
Finishing off 2
Finishing off 3
NIL
CL-USER> (defun recurse2 (n)
(format t "~&Entering at ~A" n)
(if (zerop n)
(format t "~&Reached bottom.")
(progn
(recurse2 (- n 1))
(recurse2 (- n 1))))
(format t "~&Leaving from ~A" n))
RECURSE2
CL-USER> (recurse2 1)
Entering at 1
Entering at 0
Reached bottom.
Leaving from 0
Entering at 0
Reached bottom.
Leaving from 0
Leaving from 1
NIL
and improvise from there.
Alan Crowe
Edinburgh
Scotland
viper-2
Jeff:
I forgot to edit FIB-RECUR to print the Fibonacci numbers in ascending
order, if you prefer things that way. The (VALUES) procedure at the
end of the second COND clause ensures that there is no return value
(i.e., no NIL at the end).
See chapters 7 and 22 of Practical Common Lisp by Peter Seibel for
additional iterative versions for computing Fibonacci numbers using DO
and LOOP.
>
(defun fib-recur (x &optional (y 0))
(cond ((zerop (1+ x)))
(t (print (fibber y))
(fib-recur (1- x) (1+ y))
(values))))
FIB-RECUR
>
(defun fibber (x)
(if (or (= x 0) (= x 1))
1
(+ (fibber (- x 1))
(fibber (- x 2)))))
FIBBER
>
(fib-recur 8)
1
1
2
3
5
8
13
21
34
>
agthompson
Jeff Rollin
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
Vassil Nikolov
On 23 May 2007 17:58:57 +0100, Alan Crowe <al...@cawtech.freeserve.co.uk> said:
| ...
CL-USER| (defun recurse (x)
| (format t "~&Starting on ~A." x)
| (if (zerop x)
| (format t "~&The end.")
| (recurse (- x 1)))
| (format t "~&Finishing off ~A" x))
Use TRACE instead.
---Vassil.
--
The truly good code is the obviously correct code.