Pythonの再帰とバックトラックとは？仕組みとコード例をわかりやすく解説

再帰（Recursion）とは

再帰とは、問題をより小さな単位へ分割して解決するための強力な手法です。再帰関数は自分自身を呼び出す構造を持っており、各再帰呼び出しがさらに別の再帰呼び出しを生み出していきます。

再帰関数の中核を成すのは、次の2種類のケースです。

ベースケース（基底ケース）：再帰をいつ終了するかを決める条件です。これがなければ関数は無限に呼び出され続け、スタックオーバーフローを引き起こします。
再帰ケース：自分自身の関数を呼び出す処理の部分です。

再帰が自然に活きる典型例として「階乗（factorial）」の計算が挙げられます。階乗を求める再帰アルゴリズムには、n = 0 のときに 1 を返すベースケースと、n > 0 のときに n × factorial(n-1) を計算する再帰ケースの2つのケースがあります。

バックトラック（Backtracking）とは

バックトラックは、ある計算問題への解を見つけ出すための汎用的なアルゴリズムです。解候補を少しずつ積み上げるように構築していき、そのままだと解にたどり着けないと判断された経路については、以降の処理を打ち切ります。

バックトラック最大の特徴は、以前に行った選択が誤りだと判明した際に、その選択を取り消して別の道を試せる点です。迷路の探索やパズルの求解など、組み合わせ問題で広く使われています。

実装例：階乗を求める再帰関数

以下は、階乗を計算する再帰関数の典型的な実装例です。

def factorial(n):
    # ベースケースの判定
    if n == 0:
        return 1
    # 計算と再帰呼び出し
    f = n * factorial(n - 1)
    print(f)
    return f

factorial(4)

このコードを実行すると、1、2、6、24 という数値が出力されます。4 の階乗を計算するには、最初の親呼び出しに加えて4回の再帰呼び出しが必要になります。

処理の流れを整理すると、次のようになっています。

• factorial(0)：ベースケースに該当し、1 を返す
• factorial(1) ＝ 1 × 1 ＝ 1
• factorial(2) ＝ 2 × 1 ＝ 2
• factorial(3) ＝ 3 × 2 ＝ 6
• factorial(4) ＝ 4 × 6 ＝ 24

このように、再帰では結果がベースケース側から順に遡って確定していく様子が、print文の出力からも確認できます。