Pythonで再帰関数を作成する方法｜基本の考え方と実装例を解説

再帰（Recursion）とは？

再帰とは、関数がその処理の中で自分自身を1回以上呼び出すプログラミング手法のことです。通常、その呼び出しの戻り値を利用しながら最終的な結果を返します。このように自分自身を呼び出す形で定義された関数を「再帰関数」と呼びます。

再帰関数に欠かせない「終了条件」

再帰関数をプログラムで使用するには、必ず処理が終了することが前提となります。再帰呼び出しが行われるたびに扱う問題の規模が少しずつ小さくなり、それ以上再帰せずに答えを直接求められる状態――いわゆる「ベースケース」へと近づいていくことで、関数は適切に停止します。

逆に、ベースケースに到達できないまま呼び出しが続くと、再帰は無限ループに陥り、プログラムが異常終了する原因となるので注意が必要です。

例：1からnまでの自然数の合計を求める

次のコードは、Pythonの再帰関数を使って、最初のn個の自然数の合計を計算して返すものです。

def sum_n(n):
    if n == 0:
        return 0
    else:
        return n + sum_n(n-1)

この関数を使って、最初の100個の自然数の合計と、最初の500個の自然数の合計を出力してみましょう。

print(sum_n(100))
print(sum_n(500))

実行結果

5050
125250

コードの動作を分解して理解する

sum_n(5) を例にすると、処理は次のように展開されます。

sum_n(5)
= 5 + sum_n(4)
= 5 + (4 + sum_n(3))
= 5 + (4 + (3 + sum_n(2)))
= 5 + (4 + (3 + (2 + sum_n(1))))
= 5 + (4 + (3 + (2 + (1 + sum_n(0)))))
= 5 + 4 + 3 + 2 + 1 + 0
= 15

呼び出しが重なるたびに n がひとつずつ減っていき、ベースケース（n == 0）で 0 を返した後、結果が順番に足し合わされて最終的な合計が得られます。

注意点：Pythonの再帰の深さ制限

Pythonでは、スタックオーバーフローを防ぐため、デフォルトで再帰の深さが約1000回に制限されています。そのため sum_n(500) は正常に動作しますが、sum_n(10000) のように非常に大きな値を渡すと RecursionError が発生します。深い再帰が必要な場合は、sys.setrecursionlimit() で上限を変更するか、for文などによる反復処理への書き換えを検討するとよいでしょう。