再帰呼び出し

再帰呼び出し

#

再帰呼び出しとは，ある関数が自分自身を呼び出すことを指します． 数学の漸化式をそのままプログラムで表現したものとして捉えることができます．

再帰呼び出しの例

#

\(n!\)（階乗）は，\(n\)以下の正の整数（\(1, 2, 3, …\)）をすべて掛け合わせたものです． これを数式で書くと，以下の通りです．

\[ n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1 \]

この\(n!\)を漸化式で表現すると次の通りです． ただし，\(n!\)は，\(n = 0\)のとき1，それ以外のときは\(n \times (n-1)!\)となります．

\[ n! = \bigg\lbrace \begin{array}{ll} 1 & (n = 0) \\ n \times (n-1)! & (n \geq 1) \end{array} \]

この漸化式をプログラム（factorial関数）で表現すると，\(n\)が0のときは1を返し，それ以外の時は\(n \times (n-1)!\)を返す関数を定義することになります． \(n \times (n-1)!\) の\((n-1)!\)部分，すなわち，\(n-1\)の階乗を計算する部分は，factorial関数を呼び出します． そのため，n と factorial(n-1) を掛け合わせることで階乗を計算することができます．

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

print(factorial(4))  # => 24 (4 * 3 * 2 * 1 = 24)

再帰呼び出しのシミュレーション

#

以下の画像をクリックすると，プログラムの実行箇所とその時のメモリの状態を確認できます． 最終的に 24 が出力されることをシミュレートしてください．