What is memoization?

Memoization is a technique used to optimize algorithms by storing the results of expensive function calls and reusing these results when the same inputs occur again. This technique is especially useful in dynamic programming and recursive algorithms where the same computations are performed multiple times.

Consider the Fibonacci sequence, where each number is the sum of the two preceding numbers:

def fibonacci(n, memo={}):

    if n in memo:

        return memo[n]

    if n <= 1:

        return n

    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)

    return memo[n]