再帰(再帰関数)とは?自分自身を呼ぶ仕組みを、Pythonと図解で解説

結論: 再帰は、関数が、自分自身を呼び出す書き方です。大きな問題を、同じ形の、より小さな問題に分けて解きます。必要なのは、**①これ以上は呼ばない「終了条件」**と、②呼ぶたびに終了条件へ近づくことの2つです。どちらかが欠けると、止まらずに呼び続けて、RecursionErrorになります。

再帰とは

「n の階乗(n!)」は、1からnまでを、すべて掛け合わせた数です。

• 3! = 3 × 2 × 1 = 6
• 3! は、「3 × (2 の階乗)」と言い換えられます
• 2! は、「2 × (1 の階乗)」と言い換えられます

「階乗を求める問題」が、「より小さな階乗を求める問題」の中に、入っています。この入れ子の構造を、そのままプログラムにしたのが、再帰です。

基本の形:階乗

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

print(factorial(3))   # 6

• if n <= 1: return 1:終了条件。これ以上は、自分を呼ばない
• n * factorial(n - 1):自分を呼ぶ。引数が、1つ小さくなる

関数の基本は、関数とは、条件の書き方は、条件分岐(if文)とはをご覧ください。

動きを追う:factorial(3)

1. factorial(3) は、「3 × factorial(2)」を計算しようとして、factorial(2) を呼ぶ
2. factorial(2) は、「2 × factorial(1)」を計算しようとして、factorial(1) を呼ぶ
3. factorial(1) は、終了条件に当てはまるので、1を返す
4. 結果が順に戻る:factorial(2) は 2 × 1 = 2、factorial(3) は 3 × 2 = 6

**「下へ呼び出して、上へ結果が戻る」**という二段構えが、再帰の動きです。

再帰に必要な2つと、エラー

RecursionError

def broken(n):
    return n * broken(n - 1)   # 終了条件がない

終了条件がないため、止まらずに呼び続けます。Pythonでは、呼び出しの深さに上限があり(既定で約1,000回)、超えると、次のエラーになります。

RecursionError: maximum recursion depth exceeded

エラーが出た時の確認

• 終了条件は、書いてあるか
• 呼ぶたびに、値が終了条件へ近づいているか(n - 1 を、n + 1 と書き間違えていないか)
• 途中の値を、print で表示して確認する(デバッグとは)

再帰が向く場面

「同じ形の問題が、中に入っている」構造に向きます。

ループとの使い分け

同じ階乗は、ループでも書けます。

def factorial_loop(n):
    result = 1
    for i in range(2, n + 1):
        result = result * i
    return result

迷ったら、ループで書けるものは、ループで書くのが無難です。ループの基本は、ループ(繰り返し)とはをご覧ください。

再帰が遅くなる例:フィボナッチ

フィボナッチ数(1, 1, 2, 3, 5, 8, …)を、単純な再帰で求めると、同じ計算を何度も繰り返すため、数が大きくなると、急に遅くなります。

• 計算した結果を覚えておく(メモ化)
• ループに書き換える

といった工夫で、改善できます。

まとめ

• 再帰は、関数が、自分自身を呼び出す書き方。問題を、同じ形の、より小さな問題に分ける
• 必要なのは、終了条件と、呼ぶたびに終了条件へ近づくことの2つ
• 欠けると、止まらずに呼び続け、PythonではRecursionErrorになる
• 入れ子・階層の処理に向く。単純な繰り返しは、ループのほうが安全

関連記事:ループ(繰り返し)とは、条件分岐(if文)とは、関数とは、アルゴリズムとは、デバッグとは

あわせて読みたい:スコープ(変数の有効範囲)とは