dynamic programming while this implementation of the recurrence is obviously correctit is terribly inefficient tryfor examplerunning fib( )but don' wait for it to complete the complexity of the implementation is bit hard to derivebut it is roughly (fib( )that isits growth is proportional to the growth in the value of the resultand the growth rate of the fibonacci sequence is substantial for examplefib( is , , , , , , , , if each recursive call took nanosecondfib( would take about , years to finish let' try and figure out why this implementation takes so long given the tiny amount of code in the body of fibit' clear that the problem must be the number of times that fib calls itself as an examplelook at the tree of calls associated with the invocation fib( cib( cib( cib( cib( cib( cib( cib( cib( cib( cib( cib( cib( cib( cib( cib( cib( cib( cib( cib( cib( cib( cib( cib( cib( cib( figure tree of calls for recursive fibonacci notice that we are computing the same values over and over again for example fib gets called with three timesand each of these calls provokes four additional calls of fib it doesn' require genius to think that it might be good idea to record the value returned by the first calland then look it up rather than compute it each time it is needed this is called memoizationand is the key idea behind dynamic programming figure contains an implementation of fibonacci based on this idea the function fastfib has parametermemothat it uses to keep track of the numbers it has already evaluated the parameter has default valuethe empty dictionaryso that clients of fastfib don' have to worry about supplying an initial value for memo when fastfib is called with an it attempts to look up in memo if it is not there (because this is the first time fastfib has been called with that value)an exception is raised when this happensfastfib uses the normal fibonacci recurrenceand then stores the result in memo