## 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} = 0
F_{1} = 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.

## No comments:

## Post a Comment