On May 22, 1:11 pm, 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
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?
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
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
> 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.
> 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