Algorithms For Dummies

 

   

  PART 5 

 Challenging Difficult Problems

    elif n == 1:

        return 1

    else:

        print ("lvl %i, Summing fib(%i) and fib(%i)" %

               (tab, n-1, n-2))

        return fib(n-1,tab

+1) + fib(n-2,tab+1)

The code prints the splits generated by each recursion level. The following output 

shows what happens when you call 

fib()

 with an input value of 

7

:

fib(7)

lvl 0, Summing fib(6) and fib(5)

lvl 1, Summing fib(5) and fib(4)

lvl 2, Summing fib(4) and fib(3)

lvl 3, Summing fib(3) and fib(2)

lvl 4, Summing fib(2) and fib(1)

lvl 5, Summing fib(1) and fib(0)

lvl 4, Summing fib(1) and fib(0)

lvl 3, Summing fib(2) and fib(1)

lvl 4, Summing fib(1) and fib(0)

lvl 2, Summing fib(3) and fib(2)

lvl 3, Summing fib(2) and fib(1)

lvl 4, Summing fib(1) and fib(0)

lvl 3, Summing fib(1) and fib(0)

lvl 1, Summing fib(4) and fib(3)

lvl 2, Summing fib(3) and fib(2)

lvl 3, Summing fib(2) and fib(1)

lvl 4, Summing fib(1) and fib(0)

lvl 3, Summing fib(1) and fib(0)

lvl 2, Summing fib(2) and fib(1)

lvl 3, Summing fib(1) and fib(0)

13

The output shows 20 splits. Some numbers appear more than once as part of the 

splits. It seems like an ideal case for applying dynamic programming. The follow-

ing code adds a dictionary, called 

memo

, which stores previous results. After the 

recursion splits a number, it checks whether the result already appears in the 

dictionary before starting the next recursive branch. If it finds the result, the code 

uses the precomputed result, as shown here:

memo = dict()

def fib_mem(n, tab=0):

---

CHAPTER 16