Pythonで理解する蟻本「2-1 再帰関数」(p.30)

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-1 再帰関数」(p.30)
のコードをPythonで書き直したものとなっています。

階乗を求めるコード

def fact(n):
    if n == 0:
        return 1
    return n * fact(n - 1)

フィボナッチ数列を求めるコード

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

メモ探索(メモ化再帰)によってフィボナッチ数列を求めるコード

MAX_N = 10 ** 8    # MAX_N は十分に大きい数（関数の実行時に、MAX_N >= n となるような整数）
memo = [0] * (MAX_N + 1)

def fib(n):
    if n <= 1:
        return n
    if memo[n] != 0:
        return memo[n]
    memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]