再帰呼び出し

再帰呼び出し

#

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

再帰呼び出しの例

#

\(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)!\) の部分は，階乗を計算する関数は，factorial自身です． そのため，n と factorial(n-1) を掛け合わせることで階乗を計算することができます．

なお、負の値の階乗は定義されていませんので、\(n\)が負数であった場合はエラー文を出力しましょう。 また、\(0\)の階乗は\(1\)と定義されます（\(0! = 1\)）。

def factorial(n):
    if n < 0:
        return -1 # 負数の階乗は未定義です。
    elif n == 0:
        return 1
    else:
        return n * factorial(n - 1)

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

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

#

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