This chapter is from the book
This chapter is from the book
This chapter is from the book
Recursion
There is a much more natural and elegant way to write the Fibonacci algorithm using true recursion:
(defn fib [n]
(cond
(< n 1) nil
(<= n 2) 1
:else (+ (fib (dec n)) (fib (- n 2)))))
(defn fibs [n]
(map fib (range 1 (inc n))))
The fib function should be self-explanatory by now. After all, fib(n) is just fib(n−1) + fib(n−2). Notice, however, the calls to fib are not on the tail of the function. The last thing executed by the :else clause is the + function. This means we cannot use the recur function and that TCO is not possible. This also means that the stack will grow as the algorithm proceeds.
The range function takes two arguments, a and b, and returns a list of all the integers from a to b−1. The map function takes two arguments, f and l. The f argument must be a function and the l argument must be a list. It calls f with each member of l and returns a list containing the results.
This version of fib is extraordinarily inefficient. Consider this execution profile:
fib 20 = 6765 "Elapsed time: 1.459277 msecs" fib 25 = 75025 "Elapsed time: 11.735279 msecs" fib 30 = 832040 "Elapsed time: 106.490355 msecs" fib 34 = 5702887 "Elapsed time: 735.689834 msecs"
I didn’t bother to analyze the algorithm. But a quick curve fit suggests that the algorithm is O(n3). So, as elegant as the implementation appears, it will never do.
We can vastly improve the performance by using iteration as follows:
(defn ifib
([n a b]
(if (= 0 n)
b
(recur (dec n) b (+ a b))))
([n]
(cond
(< n 1) nil
(<= n 2) 1
:else (ifib (- n 2) 1 1)))
)
The ifib function has two overloads: [n a b] and [n]. Since it is iterative, it does not grow the stack, and it is also much faster than the previous recursive version. Indeed, I believe most of that time was spent in printing rather than true computation.
ifib 20 = 6765 "Elapsed time: 0.185508 msecs" ifib 25 = 75025 "Elapsed time: 0.177111 msecs" ifib 30 = 832040 "Elapsed time: 0.14596 msecs" ifib 34 = 5702887 "Elapsed time: 0.148221 msecs"
Of course, we’ve lost a lot of the expressive power of the recursive algorithm. We can reclaim that by remembering referential transparency: In a functional language, functions always return the same values given the same inputs. Thus, it is never necessary to reevaluate a function. Once we have computed the value of (fib 20), we can remember it instead of recomputing it.
We do this by using the memoize function as follows:
(declare fib)
(defn fib-w [n]
(cond
(< n 1) nil
(<= n 2) 1
:else (+ (fib (dec n)) (fib (- n 2)))))
(def fib (memoize fib-w))
The declare function creates an unbound symbol, which can be used by other functions so long as it is bound before its use. I used declare in this case because the definition of fib comes after fib-w, and Clojure wants all names declared or defined before they are used.
The memoize function takes an argument f, which must be a function, and returns a new function g. Calls to g with argument x will call f with x if, and only if, g has never been called with x before. It then remembers those arguments and the return value. Any subsequent call to g with x will return the remembered value.
This version of the algorithm is just as fast as the iterative version because we have short-circuited the vast majority of the recursion without sacrificing the elegance of the algorithm. We pay for that with a little extra memory, but that seems a small price to pay.
fib 20 = 6765 "Elapsed time: 0.168678 msecs" fib 25 = 75025 "Elapsed time: 0.16232 msecs" fib 30 = 832040 "Elapsed time: 0.151619 msecs" fib 34 = 5702887 "Elapsed time: 0.15134 msecs"
What we have learned here is that iteration and recursion are very different approaches. Iterative functions must use tail calls to drive the iteration and should use TCO to prevent the growth of the stack. Recursive functions do not use tail calls and therefore will grow the stack. Truly recursive functions can be quite elegant, and memoization can be used to prevent that elegance from significantly affecting performance.
Although Clojure was used as the language in this chapter, the concepts are the same in virtually every other functional language, and could even be implemented in nonfunctional languages, though with a substantial loss of elegance. ;-)