Algorithms For Dummies

  Relying on Dynamic Programming 

     305

    if n==0:

        return 0

    elif n == 1:

        return 1

    else:

        if (n-1, n-2) not in memo:

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

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

            memo[(n-1,n-2)] = fib_mem(n-1,tab

+1

                          ) 

+ fib_mem(n-2,tab+1)

        return memo[(n-1,n-2)]

Using memoization, the recursive function doesn’t compute 20 additions but 

rather uses just six, the essential ones used as building blocks to solve the initial 

requirement for computing a certain number in the sequence:

fib_mem(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)

13

Looking inside the 

memo

 dictionary, you can find the sequence of sums that define 

the Fibonacci sequence starting from 

1

:

memo

{(1, 0): 1, (2, 1): 2, (3, 2): 3, (4, 3): 5, (5, 4): 8,

 (6, 5): 13}