Pythonで再帰関数を書く方法をわかりやすく解説！基本の仕組みと実例コード

再帰関数とは？

再帰関数（recursive function）とは、関数の実行中に自分自身を呼び出す関数のことです。この仕組みにより、同じ処理を何度も繰り返し実行でき、各繰り返しの結果を出力しながら最終的な答えを導き出します。再帰は「無限」の概念とも深い関係があり、呼び出しを終了させる条件（基底条件）を適切に設定することが重要です。

ここでは、整数の階乗を求める再帰関数を例に、その仕組みを解説します。

ある数の階乗とは、1からその数までのすべての整数を掛け合わせた積のことです。例えば、9の階乗（9! と表記）は次のように計算されます。

9! = 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 = 362880

例1：階乗を求める再帰関数

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

number = 9
print("The factorial of", number, "is", factorial(number))

実行結果

The factorial of 9 is 362880

上記のプログラムでは、factorial() 関数が自分自身を呼び出しているため、再帰関数として動作しています。各呼び出しでは、引数の値と「その値から1を引いた数の階乗」を掛け合わせ、引数が1になるまで処理を繰り返します。引数が1になった時点で return 1 が返され、そこから順番に掛け算の結果がさかのぼって計算されていく流れです。

再帰のイメージをつかむには、「向かい合わせに置いた2枚の鏡」を思い浮かべるとよいでしょう。鏡の間にある物体は、互いに反射し合いながら無限に映り込みます。再帰関数も同様に、自分自身の中に自分自身が現れる構造を持っています。

例2：数字を降順・昇順に出力する再帰関数

次の例では、再帰を使って数字を降順（大きい順）に出力した後、呼び出しから戻る際に昇順（小さい順）でもう一度出力しています。

def Function(x):
    if (x < 1):
        return
    else:
        print(x, end=" ")
        Function(x-1)
        print(x, end=" ")
        return

x = 5
Function(x)

実行結果

5 4 3 2 1 1 2 3 4 5

このプログラムの動きを見てみましょう。まず Function(5) が呼び出され、「5」が出力された後に Function(4) を呼び出します。これが x < 1 となるまで繰り返され、再帰が底に達した後、今度は呼び出し元へ順番に戻りながら「1 2 3 4 5」と昇順に出力されるのです。このように、再帰呼び出しの「前」と「後」でそれぞれ異なる処理を実行できる点が、再帰の面白いところです。

再帰を使う際の注意点

再帰関数を書くときは、以下のポイントに気をつけましょう。

• 終了条件を必ず設ける： 終了条件がないと無限に自分を呼び出し続け、RecursionError が発生します。
• デフォルトの再帰上限に注意： Pythonでは標準で約1000回までの再帰呼び出しに制限されています。深い再帰が必要な場合は sys.setrecursionlimit() で上限を変更できます。
• 単純なループで代替できるか検討する： 再帰は可読性やスタック消費の観点から、for文やwhile文で置き換えられるケースもあります。

階乗やフィボナッチ数列など、問題自体が再帰的な構造を持つ場合には、再帰関数を使うことでコードを簡潔かつ直感的に記述できます。ぜひ実際にコードを動かして、再帰の挙動を体感してみてください。