Recursion in Common Lisp, pushing values, and the Fibonacci Sequence

Question

This is not a homework assignment. In the following code:

(defparameter nums '())

(defun fib (number)
  (if (< number 2)
      number
    (push (+ (fib (- number 1)) (fib (- number 2))) nums))
  return nums)

(format t "~a " (fib 100))

Since I am quite inexperienced with Common Lisp, I am at a loss as to why the function does not return an value. I am a trying to print first 'n' values, e.g., 100, of the Fibonacci Sequence.

Thank you.

Answer 1

Your function unconditionally returns nums (but only if a variable called return exists). To see why, we can format it like this:

(defun fib (number)
  (if (< number 2)
    number
    (push (+ (fib (- number 1)) (fib (- number 2))) nums))
  return 
  nums)

If the number is less than 2, then it evaluates the expression number, uselessly, and throws away the result. Otherwise, it pushes the result of the (+ ....) expression onto the nums list. Then it uselessly evaluates return, throwing away the result. If a variable called return doesn't exist, that's an error situation. Otherwise, it evaluates nums and that is the return value.

In Common Lisp, there is a return operator for terminating and returning out of anonymous named blocks (blocks whose name is the symbol nil). If you define a named function with defun, then an invisible block exists which is not anonymous: it has the same name as that function. In that case, return-from can be used:

(defun function ()
  (return-from function 42) ;; function terminates, returns 42
  (print 'notreached))     ;; this never executes

Certain standard control flow and looping constructs establish a hidden anonymous block, so return can be used:

 (dolist (x '(1 2 3))
   (return 42))            ;; loop terminates, yields 42 as its result

If we use (return ...) but there is no enclosing anonymous block, that is an error.

The expression (return ...) is different from just return, which evaluates a variable named by the symbol return, retrieving its contents.

It is not clear how to repair your fib function, because the requirements are unknown. The side effect of pushing values into a global list normally doesn't belong inside a mathematical function like this, which should be pure (side-effect-free).