Memoization recursion and dynamic programming known by Python Fibonacci sequence

Introduction

This article is posted as a memo because I learned the importance of calculation ingenuity through the calculation of the Fibonacci sequence.

What is the Fibonacci sequence?

It is a sequence expressed by the formula An = An-1 + An-2 (A0 = A1 = 1).

The sequence of terms is the sum of 1 1 2 3 5 8 .... and the previous two terms.

Implementation (recursive, memoized recursion, dynamic programming)

First, implement recursively

Implemented a function to find an arbitrary term of Fibonacci sequence in python.

fib.py

def fib(n):
    if n == 0 or n == 1:
        return 1

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

This function finds the terms of any Fibonacci sequence. However, this function is computationally expensive. To find fib (5), find fib (4) and fib (3). When finding fib (4), find fib (3) and fib (2). In this case fib (3) is calculated twice. As you can see, the recursive implementation causes unnecessary calculations.

Implementation with memoization recursion

In addition to normal recursion, memoized recursion holds information about calculated terms. This time we will use the dictionary type structure of python.

fib.py

class Fib_memo:
    def __init__(self):
        self.fib_memo = {}

    def cal_fib(self, n):
        if n == 0 or n == 1:
            self.fib_memo[n] = 1
            return 1

        #Use the saved information if the term has already been calculated
        if n in self.fib_memo.keys():
            return self.fib_memo[n]
        
        self.fib_memo[n] = self.cal_fib(n-1) + self.cal_fib(n-2)
        return self.fib_memo[n]

By saving and storing the already calculated terms and using them, waste of calculation is eliminated.

Implementation with dynamic programming

In dynamic programming, the Fibonacci sequence term is calculated from the smallest. It eliminates the waste of calculation.

fib.py

def fib_dynamic(n):
    #Dictionary that holds results
    cal_result = {}

    #Initial value setting
    cal_result[0] = 1
    cal_result[1] = 1

    if n == 0 or n == 1:
        return 1

    for i in range(2, n+1):
        cal_result[i] = cal_result[i-1] + cal_result[i-2]

    return cal_result[n]

Verification

The execution cost (seconds) for the three implementations was calculated with n = 1 to 15. The resulting graph is shown below.

Normal is normal recursion, Memo is memoization recursion, and Dynamic is dynamic programming. From the graph, you can see that there is a big difference in execution speed from about n = 10.

Conclusion

From the above, it was found that the execution speed differs greatly with a simple device. Usually, I don't pay much attention to the execution speed, and it is difficult to understand the importance. From this result, I felt that it is essential to devise data structures and algorithms for heavy calculations.