How to speed up your recursive function in Python?

@lru_cache

@lru_cache(None)
def fib(n: int):
    if n < 2:
        return n 
    return fib(n - 1) + fib(n - 2)

It’s been a while I have seen @lru_cache decorator in Python. One day, I need to figure out when we use it and how it works. Today is the day. The code in the above calculates n-th the Fibonacci number.

What is the @lru_cache decorator?

Decorator to wrap a function with a memoizing callable that saves up to the ‘maxsize’ most recent calls. It can save time when an expensive or I/O bound function is periodically called with the same arguments. [3] It works in the LRU(Least Recently Used) manner. It discards an element that is accessed late.

The memoizing technique stores every result and reuses it when we call the function with the same arguments. We can frequently face while we are using dynamic programming.

How to boost recursive function?

If we call the recursive function with the same value of arguments, then we can make our algorithm fast. Using the @lru_cache decorator, it is possible to access the old value that has been evaluated. [3] Since it will save the return value on the dictionary, it consumes O(1) time to get the value.

What is the meaning of None?

If maxsize is set to None, the LRU feature is disabled and the cache can grow without bound. [3]

Terms

Decorator

In object-oriented programming, the decorator pattern is a design pattern that allows behavior to be added to an individual object, dynamically, without affecting the behavior of other objects from the same class. [1]

Fibonacci number

Each number is the sum of the two preceding ones, starting from 0 and 1. [2]

Memoizing

In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. [4]

Dynamic Programming

Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. [5]

LRU(Least Recently Used)

Discards the least recently used items first. This algorithm requires keeping track of what was used when, which is expensive if one wants to make sure the algorithm always discards the least recently used item. [6]

Reference

[1] https://en.wikipedia.org/wiki/Decorator_pattern

[2] https://en.wikipedia.org/wiki/Fibonacci_number

[3] https://docs.python.org/3/library/functools.html#functools.lru_cache

[4] https://en.wikipedia.org/wiki/Memoization

[5] https://en.wikipedia.org/wiki/Dynamic_programming

[6] https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_recently_used_(LRU)

Photo by Mario Mesaglio on Unsplash