【Python】メモ化再帰による再帰処理の効率化

現在Recursionに取り組んでいる。 そこで学んだことをメモする。

---

メモ化再帰

再帰処理において、同じ引数の計算を何度も行う場合がある。 そこで計算結果をメモとしてキャッシュして効率化をはかること。

例えば以下が計算結果をキャッシュする前。 （例としてフィボナッチ数列を挙げる）

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1

    result = fibonacci(n - 1) + fibonacci(n - 2)
    return result

フィボナッチ数列では同じ引数の計算を最大3回行う。 そのため全ての計算を再帰で行うと計算量が大幅に増えてしまう。

そこで以下のようにmemoを用意し、そこに計算結果をキャッシュする。 もし同じ引数だった場合は計算せずにキャッシュを参照することで計算を1回に減らせる。

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n == 0:
        return 0
    if n == 1:
        return 1

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