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?

Rocca

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)

Devilment

Actually, I am not allowed to use reverse function. I've to do it in a single recursive function, without using any inbuilt function like reverse. Thanks anyway. – Rocca

@Rocca You should mention restrictions in your question. I've added how to do it without an accumulator. – Devilment

Yeah, realized it later. Thanks a lot! – Rocca

Just for clarity: (fibonacci 5) returns just 5 numbers, not including the 5th fibonacci number itself (which is 5). I know OP never specified this but I thought it's worth mentioning. – Nudd

Answer 2

The program prints the nth number of Fibonacci series.

This program doesn't print anything. If you're seeing output, it's probably because you're calling it from the read-eval-print-loop (REPL), which reads a form, evaluates it, and then prints the result. E.g., you might be doing:

CL-USER> (fibonacci 4)
2

If you wrapped that call in something else, though, you'll see that it's not printing anything:

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

As you've got this written, it will be difficult to modify it to print each fibonacci number just once, since you do a lot of redundant computation. For instance, the call to

(fibonacci (- n 1))

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

(fibonacci (- n 2))

That means you probably don't want each call to fibonacci to print the whole sequence. If you do, though, note that (print x) returns the value of 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

You'll see some repeated parts there, since there's redundant computation. You can compute the series much more efficiently, however, by starting from the first two numbers, and counting up:

(defun fibonacci (n)
  (do ((a 1 b)
       (b 1 (print (+ a b)))
       (n n (1- n)))
      ((zerop n) b)))

CL-USER> (fibonacci 6)

2 
3 
5 
8 
13 
21 

Christoforo

Answer 3

An option to keep the basic structure you used is to pass an additional flag to the function that tells if you want printing 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 (+ a b)) (+ a b))))))

The idea is that when you do the two recursive calls only in the first you pass down the flag about doing the printing and in the second call instead you just pass NIL to avoid printing again.

Fuscous

Answer 4

(defun fib (n a b)

  (print (write-to-string n))

  (print b)

  (if (< n 100000)  

  (funcall (lambda (n a b) (fib n a b)) (+ n 1) b (+ a b)))  

  )

 

(defun fibstart ()

  (fib 1 0 1)

  )

Stockholder

Welcome to Stack Overflow! On Stack Overflow, the how is important, but a great part of the quality level of the site comes from the fact that people go to great lengths to explain the why. While a code-only answer get the person who asked the question past whatever hurdle they might be facing, it doesn't do them or future visitors much good in the long run. See Is there any benefit in code-only answers? – Ursulina