Pythonにおける再帰関数は、プログラムの中で自分自身を呼び出すという非常に強力な手法です。
複雑なアルゴリズムをシンプルに記述できる一方で、初心者にとっては「無限ループ」や「スタックオーバーフロー」といったエラーを引き起こしやすい難解なトピックでもあります。
この記事では、再帰関数の基本的な考え方から、現場で役立つ具体的な実装パターン、さらにはPython特有のスタック制限を回避する高度なテクニックまでを網羅して解説します。
2026年現在のモダンなPython開発においても、木構造の探索や数学的な処理において再帰は欠かせない知識と言えるでしょう。
再帰関数とは何か：基本的な概念を理解する
再帰関数とは、関数の定義の中にその関数自身を呼び出すコードが含まれている関数のことです。
この仕組みを理解する上で最も重要なのは、自分自身を呼び出すたびに「新しいタスク」がスタックに積み上がっていくというイメージを持つことです。
大きな問題を、それと同じ性質を持つ「より小さな問題」に分割して解決しようとする「分割統治法」において、再帰は非常に相性が良い手法です。
例えば、入れ子になったフォルダ構造を探索する場合、フォルダの中にフォルダがある限り、同じ探索処理を繰り返す必要があります。
このような「繰り返し」の構造を、ループ（for文やwhile文）を使わずに、関数の自己呼び出しによって表現するのが再帰の本質です。
再帰関数に必要な2つの要素
正しく動作する再帰関数を書くためには、絶対に欠かせない2つのルールが存在します。
1つ目は、「ベースケース（停止条件）」を定義することです。
ベースケースとは、これ以上自分自身を呼び出さずに処理を終了する条件のことで、これが欠けていると関数は無限に自分を呼び出し続けてしまいます。
2つ目は、「再帰ステップ」において、問題をベースケースに近づけることです。
呼び出しを繰り返すたびに引数の値が変化し、最終的に必ず停止条件に到達するように設計しなければなりません。
この2点が守られていないプログラムは、PythonにおいてRecursionErrorを引き起こす原因となります。
Pythonで再帰関数を書く：階乗計算を例に学ぶ
まずは、再帰関数の最も古典的な例である「階乗（factorial）」の計算プログラムを見ていきましょう。
階乗とは、ある正の整数 n に対して、1から n までのすべての整数を掛け合わせたものです。
例えば 5! は 5 * 4 * 3 * 2 * 1 であり、これは 5 * 4! と言い換えることができます。
この「n! = n * (n-1)!」という関係性こそが、再帰的な構造そのものです。
def factorial(n):
# ベースケース：nが1以下の場合は1を返す
if n <= 1:
return 1
# 再帰ステップ：nに (n-1)の階乗を掛ける
return n * factorial(n - 1)
# 関数の実行
result = factorial(5)
print(f"5の階乗は {result} です")5の階乗は 120 ですこのコードでは、n <= 1 になった瞬間に再帰が止まるよう設計されています。
factorial(5) を呼び出すと、内部では 5 * factorial(4) が呼ばれ、さらにその中で 4 * factorial(3) が呼ばれるという連鎖が起こります。
最終的に factorial(1) が 1 を返した瞬間、これまで積み上がった計算が逆順に処理され、最終的な答えが導き出されます。
再帰関数のメリットとデメリット
再帰関数を使うべきかどうかを判断するために、その利点と欠点を確認しておきましょう。
| 項目 | メリット | デメリット |
|---|---|---|
| コードの可読性 | 数学的な定義に近い記述ができ、コードが短くなる。 | 処理の流れが追いにくく、デバッグが難しい場合がある。 |
| データ構造への適応 | 木構造やグラフなど、再帰的なデータ構造の扱いに最適。 | 単純なループで書ける処理では、オーバーヘッドが大きくなる。 |
| メモリ消費 | なし（むしろデメリットになることが多い）。 | 呼び出しのたびにスタックフレームを消費し、メモリを圧迫する。 |
最大の特徴は、「複雑な階層構造を直感的に扱える」という点にあります。
しかし、Pythonにおいては関数の呼び出しコストが比較的高いため、パフォーマンスが最優先される場面では注意が必要です。
フィボナッチ数列とメモ化による最適化
再帰関数の弱点を学ぶために、フィボナッチ数列の計算を考えてみましょう。
フィボナッチ数列は F(n) = F(n-1) + F(n-2) という式で表されますが、これを愚直に実装すると計算効率が極めて悪くなります。
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(10))このコードでは、同じ値に対する計算が何度も繰り返し行われるため、n が大きくなると計算時間が爆発的に増加します。
このような無駄を省くためのテクニックが「メモ化（Memoization）」です。
Pythonでは、標準ライブラリの functools.lru_cache を使うことで、簡単にメモ化を導入できます。
from functools import lru_cache
@lru_cache(maxsize=None)
def fibonacci_optimized(n):
if n <= 1:
return n
return fibonacci_optimized(n - 1) + fibonacci_optimized(n - 2)
print(fibonacci_optimized(50))12586269025@lru_cache デコレータを付けるだけで、一度計算した結果が保存され、次回以降の呼び出しで再利用されるようになります。
これにより、本来なら数年もかかるような計算が、一瞬で終わるようになります。
Pythonのスタック制限とその回避策
Pythonには、システムがクラッシュするのを防ぐために「再帰回数の上限」が設けられています。
標準では1000回程度に設定されており、これを超えると RecursionError: maximum recursion depth exceeded というエラーが発生します。
深い木構造を探索する場合など、この制限が障害になることがあります。
sysモジュールで制限を引き上げる
どうしても深い再帰が必要な場合は、sys モジュールを使用して上限を変更することが可能です。
import sys
# 現在の上限を確認
print(f"現在の再帰上限: {sys.getrecursionlimit()}")
# 上限を2000に変更
sys.setrecursionlimit(2000)
print(f"変更後の再帰上限: {sys.getrecursionlimit()}")ただし、この値を安易に大きくしすぎると、OSレベルのスタック領域を使い果たし、Python自体が異常終了するリスクがあります。
上限の変更は、あくまで一時的な回避策として考えるべきです。
再帰をループ（反復処理）に書き換える
スタック制限を根本的に回避する最も確実な方法は、再帰関数を while 文や for 文を使ったループ処理に書き換えることです。
特に、自分で「スタック（リスト）」を用意して処理を管理する手法は、再帰を模倣する強力なテクニックです。
def flatten_list(nested_list):
"""入れ子になったリストを平坦化する（ループ版）"""
stack = list(reversed(nested_list))
result = []
while stack:
item = stack.pop()
if isinstance(item, list):
# リストなら中身を逆順にしてスタックに追加
stack.extend(reversed(item))
else:
result.append(item)
return result
data = [1, [2, [3, 4], 5], 6]
print(flatten_list(data))[1, 2, 3, 4, 5, 6]このように、リストをスタックとして活用することで、メモリが許す限り深い階層まで処理できるようになります。
Pythonでは末尾再帰最適化（Tail Call Optimization）が言語仕様としてサポートされていないため、この書き換え技術は非常に重要です。
実践的な応用例：ファイルシステムのディレクトリ探索
再帰が最も威力を発揮する実用的な場面の一つが、ファイルシステムの探索です。
ディレクトリの中にファイルやサブディレクトリが存在する構造は、典型的な再帰構造をしています。
以下の例では、指定したディレクトリ内のすべてのファイルサイズを合計する関数を作成します。
import os
def get_total_size(path):
total = 0
try:
for entry in os.scandir(path):
if entry.is_file():
# ファイルならサイズを加算
total += entry.stat().st_size
elif entry.is_dir():
# ディレクトリなら自分自身を呼び出してサイズを取得
total += get_total_size(entry.path)
except PermissionError:
# アクセス権限がない場合はスキップ
pass
return total
# カレントディレクトリの総サイズを表示
print(f"Total size: {get_total_size('.')} bytes")このプログラムでは、ディレクトリを見つけるたびに get_total_size を再帰的に呼び出しています。
どれほど深い階層にあっても、このシンプルなコードだけで全てのファイルを網羅できるのが再帰の強みです。
再帰関数を書く際のベストプラクティス
効果的で安全な再帰関数を記述するためのポイントをまとめます。
1. 停止条件を最初に書く
関数の冒頭で必ずベースケースをチェックするようにしましょう。
これにより、無駄な計算を防ぎ、バグの混入を最小限に抑えられます。
2. 引数を不変に保つ
再帰呼び出しに渡す引数は、各ステップで独立していることが望ましいです。
ミュータブルなオブジェクト（リストなど）を共有する場合は、意図しない副作用に注意してください。
3. デバッグ時は深さを出力する
処理が複雑になった場合は、現在の再帰の深さを引数として渡し、インデント付きでログを出力すると構造が見やすくなります。
def debug_recursive(n, depth=0):
print(" " * depth + f"call: {n}")
if n == 0: return 0
return debug_recursive(n - 1, depth + 1)
debug_recursive(3)call: 3
call: 2
call: 1
call: 0このように可視化することで、プログラムがどのように分岐しているかを直感的に把握できます。
まとめ
Pythonにおける再帰関数は、適切に使えば非常にエレガントで強力な武器になります。
まずは「停止条件」と「再帰ステップ」の基本構造をしっかりとマスターしましょう。
計算効率が問題になる場合は lru_cache によるメモ化を活用し、スタック制限が壁となる場合はループへの書き換えを検討することがプロフェッショナルなアプローチです。
再帰の概念を習得することは、単にプログラムを書くだけでなく、アルゴリズム的思考を鍛えることにも繋がります。
この記事で紹介したテクニックを駆使して、より高度なPythonプログラミングに挑戦してみてください。