Overview

再帰関数（Recursive Function）は、関数が自分自身を呼び出す手法。ハノイの塔（Tower of Hanoi）はその典型的な例。分割統治法（Divide & Conquer）や動的計画法（DP）の基礎でもある。

1.再帰関数の基本
 2.ハノイの塔
 3.再帰の計算量と問題点
 4.典型問題を解いてみる

1. 再帰関数の基本

再帰関数の 2つの重要な要素

基底条件（Base Case）
再帰を終了させる条件（例: n == 0 のとき終了）
再帰ステップ（Recursive Step）
問題を小さくして自分自身を呼び出す（例: f(n-1)）

例: 階乗（Factorial）

def factorial(n):
    if n == 0:  # 基底条件
        return 1
    return n * factorial(n - 1)  # 再帰ステップ

print(factorial(5))  # 出力: 120

factorial(5) = 5 * factorial(4)
factorial(4) = 4 * factorial(3)
… を繰り返して factorial(0) = 1 で終了

2. ハノイの塔（Tower of Hanoi）

(1) ハノイの塔のルール

ハノイの塔は 3本の棒と N 枚の異なるサイズの円盤を使う。
すべての円盤は最初に1本の棒（開始地点）に積まれている。
1回に 1枚の円盤だけ移動可能。
大きい円盤の上に小さい円盤を置くことはできない。
すべての円盤を開始地点から目的地へ移動する。

(2) ハノイの塔の考え方

N 枚の円盤を移動させるには、次の3ステップを行う。
N-1 枚を補助の棒へ移動
最大の円盤を目的の棒へ移動
補助の棒に移動させた N-1 枚を目的の棒へ移動

(3)再帰を使ったハノイの塔の実装

def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    hanoi(n - 1, source, auxiliary, target)
    print(f"Move disk {n} from {source} to {target}")
    hanoi(n - 1, auxiliary, target, source)

# 実行例: 3枚の円盤を A から C へ移動
hanoi(3, 'A', 'C', 'B')

(4)出力（N=3 の場合）

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

ポイント:
hanoi(3, 'A', 'C', 'B') の流れ：
2枚の円盤を A → B
3枚目の円盤を A → C
2枚の円盤を B → C

3. 再帰の計算量と問題点

(1)ハノイの塔の計算量

移動回数は $2^N - 1$
時間計算量は $O(2^N)$（指数時間）
N = 20 くらいまでは計算可能

(2)再帰の問題点

スタックオーバーフロー
Python では、デフォルトで 1000 回の再帰呼び出しが上限。1000 回を超えると、Python は｀RecursionError を投げる。（無限再帰を防ぐための安全機構）
sys.setrecursionlimit() で再帰回数の上限を増やせる。ただし、あまりに大きくしすぎるとメモリを大量に消費し、クラッシュのリスクがある。
ループで書き換える
例えば、フィボナッチ数列を再帰ではなくループで計算すると安全：

def fibonacci_iterative(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fibonacci_iterative(10000))  # ループなら深い再帰を回避できる

メモ化再帰（Memoization）で最適化できる場合もある
フィボナッチ数列をメモ化して最適化すれば、再帰の深さを抑えられる
@lru_cache を使うと、計算済みの値をキャッシュして無駄な再帰を削減:

from functools import lru_cache

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

print(fibonacci(1000))  # 1000回の再帰でも大丈夫

4. 典型問題を解いてみる

例題1. 階乗の再帰計算

問題: N! を求めよ。

参考： ABC315 B - Factorial

回答　

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

N = int(input())
print(factorial(N))

例題2. 再帰を使ったフィボナッチ数列

問題: F(n) = F(n-1) + F(n-2)（F(0) = 0, F(1) = 1）を求めよ。

参考： ABC318 B - Fibonacci

回答　

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

N = int(input())
print(fibonacci(N))

例題3. 再帰でハノイの塔

問題: N 枚のハノイの塔を A から C へ移動する手順を出力せよ。

参考： ABC319 C - Hanoi Tower

回答　

def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    hanoi(n - 1, source, auxiliary, target)
    print(f"Move disk {n} from {source} to {target}")
    hanoi(n - 1, auxiliary, target, source)

N = int(input())
hanoi(N, 'A', 'C', 'B')

例題4. 再帰で GCD（最大公約数）を求める

問題: GCD(A, B) を再帰を使って求めよ。

参考： ABC320 B - GCD with Recursion

回答　

def gcd_recursive(a, b):
    if b == 0:
        return a
    return gcd_recursive(b, a % b)

A, B = map(int, input().split())
print(gcd_recursive(A, B))