Geek Answers Handbook

Creating a Fibonacci series in Lisp using recursion?

I am new to LISP. I am trying to write a function in CLISP to generate the first n numbers of Fibonacci series.

This is what I have done so far.

(defun fibonacci(n) (cond ((eq n 1) 0) ((eq n 2) 1) ((+ (fibonacci (- n 1)) (fibonacci (- n 2))))))))

The program prints the nth number of Fibonacci series. I am trying to change it so that it prints a series, not just the nth member.

Is it possible to do this in only one recursive function using only the main functions?

+7
source share
3 answers

Yes:

 (defun fibonacci (n &optional (a 0) (b 1) (acc ())) (if (zerop n) (nreverse acc) (fibonacci (1- n) b (+ ab) (cons a acc)))) (fibonacci 5) ; ==> (0 1 1 2 3)

The logic behind this is that you need to know the two previous numbers in order to generate the next.

 a 0 1 1 2 3 5 ... b 1 1 2 3 5 8 ... new-b 1 2 3 5 8 13 ...

Instead of returning only one result, I accumulate all a -s until n becomes zero.

EDIT Without brute force, this is a bit more inefficient:

 (defun fibonacci (n &optional (a 0) (b 1)) (if (zerop n) nil (cons a (fibonacci (1- n) b (+ ab))))) (fibonacci 5) ; ==> (0 1 1 2 3)
+11
source

The program prints the nth number of Fibonacci series.

This program does not print anything. If you see the output, probably because you are calling it from read-eval- print -loop (REPL), which reads the form, evaluates it, and then prints the result. For example, you can do:

 CL-USER> (fibonacci 4) 2

If you wrapped this call in another, you will see that it does not print anything:

 CL-USER> (progn (fibonacci 4) nil) NIL

Since you have written this, it will be difficult to change it to print each fibonacci number only once, since you are doing a lot of redundant calculations. For example, a call

 (fibonacci (- n 1))

will compute (fibonacci (- n 1)) , but so will the direct call

 (fibonacci (- n 2))

This means that you probably don't want every fibonacci call to print the entire sequence. If you do this, note that (print x) returns the value x , so you can simply do:

 (defun fibonacci(n) (cond ((eq n 1) 0) ((eq n 2) 1) ((print (+ (fibonacci (- n 1)) (fibonacci (- n 2))))))) 
 CL-USER> (progn (fibonacci 6) nil) 1 2 1 3 1 2 5 NIL

Here you will see several repeating parts, as there is redundant computation. However, you can calculate the series much more efficiently, starting with the first two numbers and counting:

 (defun fibonacci (n) (do ((a 1 b) (b 1 (print (+ ab))) (nn (1- n))) ((zerop n) b))) 
 CL-USER> (fibonacci 6) 2 3 5 8 13 21
+4
source

The ability to save the basic structure you used is to pass an additional flag to a function that tells you whether you want to print or not:

 (defun fibo (n printseq) (cond ((= n 1) (if printseq (print 0) 0)) ((= n 2) (if printseq (print 1) 1)) (T (let ((a (fibo (- n 1) printseq)) (b (fibo (- n 2) NIL))) (if printseq (print (+ ab)) (+ ab))))))

The idea is that when you make two recursive calls only in the first, you pass the flag to print and in the second call, instead you just pass NIL to avoid printing again.

+2
source

More articles:


All Articles