Python 再帰完全マスター: 関数が自分自身を呼び出す仕組み

Python 再帰をマスターする

Python関数が自分自身を呼び出す仕組み、再帰のメカニクス、安全で効率的な再帰コードを書くベストプラクティスを学びます。

再帰とは？

再帰は、問題を同じ問題のより小さなインスタンスの観点から定義する技法です。

古典的な例は、互いに向き合った2つの平行鏡。各像は他方の再帰的な反射です。

---

Python 再帰関数

Pythonでは関数は他の関数を呼び出せますが、自分自身を呼び出すこともできます。このような構造を再帰関数と呼びます。

以下の画像は、recurseというシンプルな再帰関数のコールスタックを示しています：

以下は古典的例: 階乗関数の再帰実装。正の整数xまでのすべての正の整数の積を返します。

再帰関数の例

def factorial(x):
    """Recursively compute the factorial of a positive integer."""
    if x == 1:
        return 1
    return x * factorial(x - 1)
num = 3
print("The factorial of", num, "is", factorial(num))

出力

The factorial of 3 is 6

ここではfactorial()が自分自身を呼び出すため再帰関数。ベースケースx == 1に達するまで再帰呼び出しを繰り返します。

正の整数で呼び出すと、値をデクリメントしながら繰り返し自分を呼び出します：

factorial(3) # 1回目の呼び出し(3)
3 * factorial(2) # 2回目の呼び出し(2)
3 * 2 * factorial(1) # 3回目の呼び出し(1)
3 * 2 * 1 # 3回目からリターン
3 * 2 # 2回目からリターン
6 # 1回目からリターン

以下はこのステップバイステッププロセスの視覚表現：

入力値が基本条件(この場合x == 1)に達すると再帰終了。すべての再帰関数にはこの停止基準が必要。なければ無限に続き、最終的にコールスタックを枯渇させます。

Pythonはデフォルト1000の最大再帰深度を強制し、無限再帰によるインタプリタクラッシュを防止。この制限超過でRecursionError発生：

def recursor():
    recursor()
recursor()

出力

Traceback (most recent call last):
File "<string>", line 3, in <module>
File "<string>", line 2, in a
File "<string>", line 2, in a
File "<string>", line 2, in a
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

sys.setrecursionlimit()で再帰制限をプログラム的に調整可能ですが、スタックオーバーフローを避けるため慎重に。

---

再帰の利点

1. 再帰的解法はしばしば簡潔で読みやすく、特に再帰的に表現される問題に自然。
2. 複雑なタスクをより単純なサブ問題に分解するエレガントな手法を提供。
3. 数列生成(フィボナッチ、順列など)はネストループより再帰で直截的。

---

再帰の欠点

1. 再帰ロジックは初心者には追跡・推論が難しい場合がある。
2. 各再帰呼び出しはスタックスペースを消費。深い再帰はメモリ集約的で反復的代替より遅い傾向。
3. 階層化されたコールスタックのためデバッグが困難。

実践では、コードがより明確で保守しやすくなり、入力サイズが中程度なら再帰を選択。非常に大きな入力には反復的アプローチや末尾再帰最適化(サポートされている場合)が望ましい。