Fibonacci Numbers as a Dynamic Programming Problem

Early in our education as Lisp programmers we all learn the naturalness and power of recursion. We also learn that it can sometimes be the spectacularly wrong way of doing things. The canonical example is implementing the Fibonacci function

recursively.

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

This is a bad implementation because it repeatedly calculates the F(n) resulting in an exponential running time and an O(n) space requirement. But if we (slightly) rewrite the definition as a recurrence relation

F₀ = 0 F₁ = 1 F_n = F_n-1 + F_n-2 we notice that we have the makings for a classical Dynamic Programming solution: a recursion relation that specifies the solution of the problem in terms of one or more subproblems. It's straightforward to implement this solution

(defun fib-dp (n)
(let ((F (make-array (max 2 (1+ n)))))
  (setf (aref F 0) 0)
  (setf (aref F 1) 1)
  (do
   ((i 2 (1+ i)))
   ((> i n) (aref F n))
    (setf (aref F i) (+ (aref F (- i 1)) (aref F (- i 2)))))))

Here the amount of space and the amount of work are both O(n). We can make a further optimization if we notice that we don't need to store all the values of F, just the last two. This gives us a solution that is O(n) in time and O(1) in space.

(defun fib-opt (n)
(if (<= n 1)
    n
    (let ((F-last 1) (F-second-last 0) temp)
      (do
       ((i 2 (1+ i)))
       ((> i n) F-last)
        (setf temp F-last
              F-last (+ F-last F-second-last)
              F-second-last temp)))))

Finally, we can come full circle and reintroduce recursion. Because this is tail recursion the solution still uses constant space—at least for those Lisps (i.e. pretty much all modern Lisps) that optimize tail recursion.

(defun fib-opt2 (n)
(if (<= n 1)
    n
    (labels ((fib (n F-last F-second-last)
               (if (zerop n)
                   F-last
                   (fib (1- n) (+ F-last F-second-last) F-last))))
      (fib (1- n)  1 0))))

None of this is earth shattering, of course, but it's a nice illustration of how shifting your viewpoint a little can help you arrive at what SICP describes as a non-straightforward solution.