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

An obvious approach to computing fibonacci numbers is this:

(defun fib (n)
  (if (< n 2)
      n
    (+ (fib (- n 1)) (fib (- n 2)))))

(defun fibs (n)
  (loop for i from 1 below n
        collect (fib i)))

A little thought should tell you why no approach like this is going to help you compute the first 100 Fibonacci numbers: the time taken to compute (fib n) is equal to or a little more than the time taken to compute (fib (- n 1)) plus the time taken to compute (fib (- n 2)): this is exponential (see this stack overflow answer).

A good solution to this is memoization: the calculation of (fib n) repeats subcalculations a huge number of times, and if we can just remember the answer we computed last time we can avoid doing so again.

(An earlier version of this answer has an overcomplex macro here: something like that may be useful in general but is not needed here.)

Here is how you can memoize fib:

(defun fib (n)
  (check-type n (integer 0) "natural number")
  (let ((so-far '((2 . 1) (1 . 1) (0 . 0))))
    (labels ((fibber (m)
               (when (> m (car (first so-far)))
                 (push (cons m (+ (fibber (- m 1))
                                  (fibber (- m 2))))
                       so-far))
               (cdr (assoc m so-far))))
      (fibber n))))

This keeps a table – an alist – of the results it has computed so far, and uses this to avoid recomputation.

With this memoized version of the function:

> (time (fib 1000))
Timing the evaluation of (fib 1000)

User time    =        0.000
System time  =        0.000
Elapsed time =        0.000
Allocation   = 101944 bytes
0 Page faults
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

The above definition uses a fresh cache for each call to fib: this is fine, because the local function, fibber does reuse the cache. But you can do better than this by putting the cache outside the function altogether:

(defmacro define-function (name expression)
  ;; Install EXPRESSION as the function value of NAME, returning NAME
  ;; This is just to avoid having to say `(setf ...)`: it should
  ;; probably do something at compile-time too so the compiler knows
  ;; the function will be defined.
  `(progn
     (setf (fdefinition ',name) ,expression)
     ',name))

(define-function fib
  (let ((so-far '((2 . 1) (1 . 1) (0 . 0))))
    (lambda (n)
      (block fib
        (check-type n (integer 0) "natural number")
        (labels ((fibber (m)
                   (when (> m (car (first so-far)))
                     (push (cons m (+ (fibber (- m 1))
                                      (fibber (- m 2))))
                           so-far))
                   (cdr (assoc m so-far))))
          (fibber n))))))

This version of fib will share its cache between calls, which means it is a little faster, allocates a little less memory but may be less thread-safe:

> (time (fib 1000))
[...]
Allocation   = 96072 bytes
[...]

> (time (fib 1000))
[...]
Allocation   = 0 bytes
[...]

Interestingly memoization was invented (or at least named) by Donald Michie, who worked on breaking Tunny (and hence with Colossus), and who I also knew slightly: the history of computing is still pretty short!

---

Note that memoization is one of the times where you can end up fighting a battle with the compiler. In particular for a function like this:

(defun f (...)
  ...
  ;; no function bindings or notinline declarations of F here
  ...
  (f ...)
  ...)

Then the compiler is allowed (but not required) to assume that the apparently recursive call to f is a recursive call into the function it is compiling, and thus to avoid a lot of the overhead of a full function call. In particular it is not required to retrieve the current function value of the symbol f: it can just call directly into the function itself.

What this means is that an attempt to write a function, memoize which can be used to mamoize an existing recursive function, as (setf (fdefinition 'f) (memoize #'f)) may not work: the function f still call directly into the unmemoized version of itself and won't notice that the function value of f has been changed.

This is in fact true even if the recursion is indirect in many cases: the compiler is allowed to assume that calls to a function g for which there is a definition in the same file are calls to the version defined in the file, and again avoid the overhead of a full call.

The way to deal with this is to add suitable notinline declarations: if a call is covered by a notinline declaration (which must be known to the compiler) then it must be made as a full call. From the spec:

A compiler is not free to ignore this declaration; calls to the specified functions must be implemented as out-of-line subroutine calls.

What this means is that, in order to memoize functions you have to add suitable notinline declarations for recursive calls, and this means that memoizing either needs to be done by a macro, or must rely on the user adding suitable declarations to the functions to be memoized.

This is only a problem because the CL compiler is allowed to be smart: almost always that's a good thing!

Answer 2

So you might know that if you know the two previous numbers you can compute the next. What comes after 3, 5? If you guess 8 you have understood it. Now if you start with 0, 1 and roll 1, 1, 1, 2, etc you collect the first variable until you have the number of numbers you'd like:

(defun fibs (elements)
  "makes a list of elements fibonacci numbers starting with the first"
  (loop :for a := 0 :then b
        :for b := 1 :then c
        :for c := (+ a b)
        :for n :below elements
        :collect a))

(fibs 10)
; ==> (0 1 1 2 3 5 8 13 21 34)

Every form in Common Lisp "returns" a value. You can say it evaluates to. eg.

(if (< a b)
    5
    10)

This evaluates either to 5 or 10. Thus you can do this and expect that it evaluates to either 15 or 20:

(+ 10 
   (if (< a b)
       5
       10))

You basically want your functions to have one expression that calculates the result. eg.

(defun fib (n)
  (if (zerop n)
      n
      (+ (fib (1- n)) (fib (- n 2)))))

This evaluates to the result og the if expression... loop with :collect returns the list. You also have (return expression) and (return-from name expression) but they are usually unnecessary.

Answer 3

Your global variable num is actually not that a bad idea.

It is about to have a central memory about which fibonacci numbers were already calculated. And not to calculate those already calculated numbers again.

This is the very idea of memoization.

But first, I do it in bad manner with a global variable.

Bad version with global variable *fibonacci*

(defparameter *fibonacci* '(1 1))

(defun fib (number)
  (let ((len (length *fibonacci*)))
    (if (> len number)
        (elt *fibonacci* (- len number 1)) ;; already in *fibonacci*
        (labels ((add-fibs (n-times)
                   (push (+ (car *fibonacci*)
                            (cadr *fibonacci*))
                         *fibonacci*)
                   (cond ((zerop n-times) (car *fibonacci*))
                         (t (add-fibs (1- n-times))))))
          (add-fibs (- number len))))))

;;> (fib 10)
;;  89
;;> *fibonacci*
;;  (89 55 34 21 13 8 5 3 2 1 1)

Good functional version (memoization)

In memoization, you hide the global *fibonacci* variable into the environment of a lexical function (the memoized version of a function).

(defun memoize (fn)
  (let ((cache (make-hash-table :test #'equal)))
    #'(lambda (&rest args)
        (multiple-value-bind (val win) (gethash args cache)
          (if win
              val
              (setf (gethash args cache)
                    (apply fn args)))))))

(defun fib (num)
  (cond ((zerop num) 1)
        ((= 1 num) 1)
        (t (+ (fib (- num 1))
              (fib (- num 2))))))

The previously global variable *fibonacci* is here actually the local variable cache of the memoize function - encapsulated/hidden from the global environment, accessible/look-up-able only through the function fibm.

Applying memoization on fib (bad version!)

(defparameter fibm (memoize #'fib))

Since common lisp is a Lisp 2 (separated namespace between function and variable names) but we have here to assign the memoized function to a variable, we have to use (funcall <variable-name-bearing-function> <args for memoized function>).

(funcall fibm 10) ;; 89

Or we define an additional

(defun fibm (num)
  (funcall fibm num))

and can do

(fibm 10)

• However, this saves/memoizes only the out calls e.g. here only the Fibonacci value for 10. Although for that, Fibonacci numbers for 9, 8, ..., 1 are calculated, too. To make them saved, look the next section!

Applying memoization on fib (better version by @Sylwester - thank you!)

(setf (symbol-function 'fib) (memoize #'fib))

Now the original fib function is the memoized function, so all fib-calls will be memoized. In addition, you don't need funcall to call the memoized version, but just do

(fib 10)

Answer 4

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).