Generating Fibonacci series in Lisp using recursion?

Question

I'm a newbie in LISP. I'm trying to write a function in CLISP to generate the first n numbers of Fibonacci series.

This is what I've 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'm trying to modify it so that it would print the series, and not just the nth term.

Is it possible to do so in just a single recursive function, using just the basic functions?

Answer 1

Yes:

(defun fibonacci (n &optional (a 0) (b 1) (acc ()))
  (if (zerop n)
      (nreverse acc)
      (fibonacci (1- n) b (+ a b) (cons a acc))))

(fibonacci 5) ; ==> (0 1 1 2 3)

The logic behind it is that you need to know the two previous numbers 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 just one result I accumulate all the a-s until n is zero.

EDIT Without reverse it's a bit more inefficient:

(defun fibonacci (n &optional (a 0) (b 1))
  (if (zerop n)
      nil
      (cons a (fibonacci (1- n) b (+ a b)))))

(fibonacci 5) ; ==> (0 1 1 2 3)