Python Data Structures and Algorithms

The Memoization technique

Let's generate the Fibonacci series to the fifth term:

    1 1 2 3 5

A recursive style of a program to generate the sequence is as follows:

    def fib(n):         if n <= 2:             return 1         else:             return fib(n-1) + fib(n-2) 

The code is very simple but a little tricky to read because of the recursive calls being made that end up solving the problem.

When the base case is met, the fib() function returns 1. If n is equal to or less than 2, the base case is met.

If the base case is not met, we will call the fib() function again and this time supply the first call with n-1 and the second with n-2:

    return fib(n-1) + fib(n-2) 

The layout of the strategy to solve the i^th term in the Fibonacci sequence is as follows:

A careful observation ...