1. 1. In a word

Memoization using the decorator @lru_cache was faster than programmatic memoization.

2. Sum of Fibonacci sequences

The sum of the Fibonacci sequences is calculated recursively by the following three methods, and the number of times the recursive function is called and the processing time are recorded. (The environment is Google Colaboratory.) (1) Ordinary recursion (2) Memoization recursion (3) LRU cache @lru_cache

3. 3. Ordinary recursion

First, let's find the sum of the Fibonacci sequences with an ordinary recursive function and measure it.

%%time
fib_cnt=0
def fib(n):
    global fib_cnt
    fib_cnt+=1
    if n<=1:
        return n
    return fib(n-1)+fib(n-2)
fib1=fib(35)
print('fib1=',fib1)
print('fib1_cnt=',fib_cnt)

The execution result is as follows. Well, it takes time.

fib1= 9227465
fib1_cnt= 29860703
CPU times: user 4.93 s, sys: 5 ms, total: 4.94 s
Wall time: 4.94 s

4. Memoization recursion

Next, let's find and measure the sum of the Fibonacci sequences by memoization recursion.

%%time
fib2_cnt=0
def fib2(n):
    memo=[0]*(n+1)
    def fib3(n):
        global fib2_cnt
        fib2_cnt+=1
        if n<=1:
            return n
        if memo[n]!=0:
            return memo[n]
        memo[n]=fib3(n-1)+fib3(n-2)
        return memo[n]
    return fib3(n)
fib2=fib2(35)
print('fib2=',fib2)
print('fib2_cnt=',fib2_cnt)

The execution result is as follows. Naturally, it will be faster.

fib2= 9227465
fib2_cnt= 69
CPU times: user 0 ns, sys: 1.69 ms, total: 1.69 ms
Wall time: 2.74 ms

What is worrisome is the number of times it is called. Since it is a Fibonacci sequence, it is the sum of the previous two numbers, or in the case of the sum of Fibonacci sequences up to 35, it is called 69 times, which is about double.

5. LRU cache @lru_cache

Finally, let's try memoization using LRU cache @lru_cache. LRU is an abbreviation for Least Recently Used. It means that I used it most recently.

%%time
from functools import lru_cache
fib4_cnt=0
@lru_cache(maxsize=None)
def fib4(n):
    global fib4_cnt
    fib4_cnt+=1
    if n<=1:
        return n
    return fib4(n-1)+fib4(n-2)
fib4=fib4(35)
print('fib4=',fib4)
print('fib4_cnt=',fib4_cnt)

In this case, the number of calls is 36 from 0 to 35. Called less often than recursion in the previous program.

fib4= 9227465
fib4_cnt= 36
CPU times: user 1.74 ms, sys: 4 µs, total: 1.75 ms
Wall time: 1.61 ms

6. Summary

Due to the structure of the program, in this example, the LRU cache @lru_cache is faster than the memoization recursion in the program. It may be good to write the program well, but it turns out that the LRU cache is lean.