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! を求めよ。
回答
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）を求めよ。
回答
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 へ移動する手順を出力せよ。
回答
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) を再帰を使って求めよ。
回答
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))