再帰とバックトラッキング

再帰の基礎

再帰関数は、チェーンを停止する 基本ケースに達するまで、問題の小さいバージョンで自分自身を呼び出します。

すべての再帰には次の 2 つのことが必要です。

1. 基本ケース - 直接返す最も単純な入力。
2. 再帰的なケース - 問題を細分化し、自分自身に電話をかけます。

def factorial(n):
    if n <= 1:        # base case
        return 1
    return n * factorial(n - 1)  # recursive case

コールスタック - 視覚化

各再帰呼び出しは、フレームを呼び出しスタックにプッシュします。基本ケースに戻ると、フレームは逆の順序でポップされます。

factorial(4)
  → factorial(3)
    → factorial(2)
      → factorial(1) → returns 1
    ← returns 2
  ← returns 6
← returns 24

基本ケースがない場合、スタックはオーバーフローします。 Python のデフォルトの再帰制限は 1,000 フレームです。

フィボナッチ - 古典的なトラップ

単純な再帰フィボナッチは、同じ部分問題を再計算するため、O(2ⁿ) です。メモ化はこれを O(n) 時間と空間で修正します。

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

バックトラッキング - すべて試してから元に戻す

バックトラッキングは、ひねりを加えた再帰です。選択を行い、再帰し、次のオプションを試す前に選択を元に戻します。迷路を探索するようなものだと考えてください。前に歩いて、行き止まりに突き当たり、戻って、次の道を試してください。

バックトラッキングテンプレート

def backtrack(state, choices):
    if is_solution(state):
        result.append(state.copy())
        return
    for choice in choices:
        if is_valid(choice):
            state.add(choice)       # choose
            backtrack(state, ...)   # explore
            state.remove(choice)    # un-choose

この 3 ステップのパターン (選択、探索、選択を解除) は、ほぼすべてのバックトラッキング問題の根幹です。

順列

[1, 2, 3] のすべての順序を生成します。各レベルで、未使用の番号を選択し、再帰的に選択し、選択を解除します。

         []
      /   |   \
    [1]  [2]  [3]
    / \   ...
 [1,2] [1,3]
   |      |
[1,2,3] [1,3,2]  ... (6 total)