再帰呼び出し

再帰呼び出し
#

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

再帰呼び出しの例 1: 階乗
#

\(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)

基底条件と再帰条件
#

再帰関数には、必ず次の 2 つの部分があります。

基底条件（base case）: 再帰呼び出しをせずに答えを返す部分です。factorial では、n == 0 のときに 1 を返す部分がこれにあたります。終了条件とも呼びます。
再帰条件（recursive case）: 自分自身を呼び出す部分です。ただし、基底条件に 近づく 引数で呼び出さなければなりません。factorial(n) は factorial(n - 1) を呼び出すので、n は 1 ずつ減って必ず 0 に到達します。

どちらかが欠けていると、再帰呼び出しは止まりません。何が起きるかは、次のページの再帰の練習で実際に確かめます。