再帰関数 — 自分自身を呼び出す関数
このトピックを終えると
再帰関数の仕組みを説明でき、終了条件（ベースケース）の重要性を理解し、簡単な再帰問題を自分で解くことができます。
再帰とは何か
再帰（recursion）とは、関数が自分自身を呼び出すことです。
def countdown(n): if n <= 0: print("Launch!") return print(n) countdown(n - 1) # 自分自身を呼び出す
countdown(5)# 5# 4# 3# 2# 1# Launch!countdown(5)がcountdown(4)を呼び、countdown(4)がcountdown(3)を呼び… countdown(0)になると、"Launch!"と出力して停止します。
これが再帰のすべてです。2つの要素があります。
- 終了条件（ベースケース）:
if n <= 0— これ以上呼び出さない条件 - 再帰ステップ（再帰ケース）:
countdown(n - 1)— 自分自身を呼び出すが、問題をより小さくする
なぜ終了条件が不可欠なのか
終了条件がない場合、無限に自分自身を呼び出し続けます。
def infinite(): print("Help!") infinite() # 永遠に呼び出す
infinite()# Help!# Help!# Help!# ...# RecursionError: maximum recursion depth exceededPythonでは、基本的に1,000回までしか再帰を許可しません。それ以上になると、RecursionErrorで強制終了します。これは、無限再帰によってメモリが使い果たされるのを防ぐための安全装置です。
階乗 — 再帰の教科書的な例
5! = 5 × 4 × 3 × 2 × 1 = 120
階乗を再帰的に考えると、5! = 5 × 4!となります。
def factorial(n): # ベースケース if n <= 1: return 1 # 再帰ケース return n * factorial(n - 1)
print(factorial(5)) # 120呼び出しのプロセスを追うと：
factorial(5)
→ 5 * factorial(4)
→ 4 * factorial(3)
→ 3 * factorial(2)
→ 2 * factorial(1)
→ 1 (ベースケース！)
← 2 * 1 = 2
← 3 * 2 = 6
← 4 * 6 = 24
← 5 * 24 = 120関数が「深く入り込み」、結果を「再び戻る」構造です。
コールスタック — 再帰が動作する仕組み
関数が呼び出されるたびに、コンピュータは**スタック（stack）**と呼ばれるメモリ空間に現在の状態を保存します。
factorial(5) の呼び出し → スタック: [factorial(5)]
factorial(4) の呼び出し → スタック: [factorial(5), factorial(4)]
factorial(3) の呼び出し → スタック: [factorial(5), factorial(4), factorial(3)]
factorial(2) の呼び出し → スタック: [factorial(5), factorial(4), factorial(3), factorial(2)]
factorial(1) の呼び出し → スタック: [factorial(5), factorial(4), factorial(3), factorial(2), factorial(1)]
factorial(1) の戻り値 → スタック: [factorial(5), factorial(4), factorial(3), factorial(2)]
factorial(2) の戻り値 → スタック: [factorial(5), factorial(4), factorial(3)]
...再帰が深くなるほど、スタックが積み重なります。Pythonのデフォルトの制限が1,000であるのは、スタックごとにメモリを使用するため、深すぎるとメモリが不足するのを防ぐためです。
フィボナッチ数 — 再帰の落とし穴
def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2)
print(fib(10)) # 55print(fib(30)) # 832040 — しかし遅い！# print(fib(50)) # 終わらない…コードは簡潔ですが、fib(50)は永遠に終わりません。同じ値を繰り返し計算するためです。
fib(5)
├── fib(4)
│ ├── fib(3)
│ │ ├── fib(2) ← 繰り返し
│ │ └── fib(1)
│ └── fib(2) ← 繰り返し
└── fib(3) ← 繰り返し
├── fib(2) ← 繰り返し
└── fib(1)fib(2)が何度も計算されます。fib(30)では数百万回、fib(50)では数十億回の重複計算が発生します。
メモ化で解決
from functools import lru_cache
@lru_cache(maxsize=None)def fib_fast(n): if n <= 1: return n return fib_fast(n - 1) + fib_fast(n - 2)
print(fib_fast(50)) # 12586269025 — 瞬時！print(fib_fast(100)) # 354224848179261915075@lru_cacheは、すでに計算した結果を保存しておき、同じ引数で呼び出された場合、保存された値を返します。重複計算がなくなるため、O(2^n)がO(n)に減少します。
再帰 vs 繰り返し
同じ問題を繰り返し（ループ）でも解くことができます。
# 再帰def factorial_rec(n): if n <= 1: return 1 return n * factorial_rec(n - 1)
# 繰り返しdef factorial_iter(n): result = 1 for i in range(2, n + 1): result *= i return result| 比較 | 再帰 | 繰り返し |
|---|---|---|
| 可読性 | 問題の構造が再帰的であれば直感的 | 単純な繰り返しはより明確 |
| パフォーマンス | コールスタックのオーバーヘッドがある | 一般的に高速 |
| メモリ | スタックの深さに応じて使用 | O(1) |
| 適切な問題 | ツリー探索、分割統治、順列/組み合わせ | 単純な繰り返し、累積計算 |
ルール: 問題の構造が自然に再帰的である場合（ツリー、グラフ、分割統治）、再帰を使用し、単純な繰り返しである場合はforループを使用します。
実践例 — ディレクトリの探索
import os
def list_all_files(directory, indent=0): """再帰的にディレクトリツリー内のすべてのファイルをリスト表示します。""" items = sorted(os.listdir(directory)) for item in items: path = os.path.join(directory, item) print(" " * indent + item) if os.path.isdir(path): list_all_files(path, indent + 1) # サブディレクトリ → 再帰
list_all_files("project")# project# app.js# routes# users.js# posts.js# public# css# style.css# index.htmlフォルダの中にフォルダがあり、その中にさらにフォルダがある構造 — これが典型的な再帰問題です。「何段階まであるかは分からないが、同じパターンが繰り返される」場合は再帰が自然です。
主要なまとめ
| 概念 | まとめ |
|---|---|
| 再帰 | 関数が自分自身を呼び出す |
| ベースケース | これ以上再帰しない終了条件（必須） |
| 再帰ケース | 問題をより小さくして自分自身を呼び出す |
| コールスタック | 呼び出しごとにメモリに状態を保存（Pythonの制限は1,000） |
| メモ化 | 重複計算の防止（@lru_cache） |
再帰を初めて見たとき、「関数が自分自身を呼び出すと無限ループになるのではないか？」という疑問が生じます。重要なのは、毎回問題がより小さくなり、最終的に終了条件に到達するということです。このパターンを理解すれば、ツリー探索、ソート（マージソート）、組み合わせ/順列、グラフ探索（DFS）など、多くのアルゴリズムを自然に理解できます。
実践パターン — ネストされた辞書の探索
JSONや設定ファイルで、深さが不明なネストされた構造に遭遇した場合、再帰が自然です。
def flatten_dict(d, prefix=""): result = {} for key, value in d.items(): full_key = f"{prefix}.{key}" if prefix else key if isinstance(value, dict): result.update(flatten_dict(value, full_key)) else: result[full_key] = value return result
config = { "database": { "host": "localhost", "port": 5432, "credentials": { "user": "admin", "password": "secret" } }, "debug": True}
print(flatten_dict(config))# {# 'database.host': 'localhost',# 'database.port': 5432,# 'database.credentials.user': 'admin',# 'database.credentials.password': 'secret',# 'debug': True# }このパターンは、ログシステム、設定管理、Elasticsearchインデックス作成などでよく使用されます。