《アルゴリズムを学ぶ》17.再帰関数（ハノイの塔）

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

[1.再帰関数の基本](#1-再帰関数の基本)
[2.ハノイの塔](#2-ハノイの塔tower-of-hanoi)
[3.再帰の計算量と問題点](#3-再帰の計算量と問題点)
[4.典型問題を解いてみる](#4-典型問題を解いてみる)

# 1. 再帰関数の基本
再帰関数の 2つの重要な要素

1. 基底条件（Base Case）
再帰を終了させる条件（例: n == 0 のとき終了）

2. 再帰ステップ（Recursive Step）
問題を小さくして 自分自身を呼び出す（例: f(n-1)）

例: 階乗（Factorial）
```python
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)再帰を使ったハノイの塔の実装
```python
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 の場合）
```css
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()` で再帰回数の上限を増やせる。ただし、あまりに大きくしすぎるとメモリを大量に消費し、クラッシュのリスクがある。
- ループで書き換える
例えば、フィボナッチ数列 を 再帰ではなくループ で計算すると安全：
```python
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` を使うと、計算済みの値をキャッシュして無駄な再帰を削減:
```python
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](https://atcoder.jp/contests/abc315/tasks/abc315_b)
<details><summary> 回答　</summary>

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

N = int(input())
print(factorial(N))
```
</details>

### 例題2. 再帰を使ったフィボナッチ数列
**問題: F(n) = F(n-1) + F(n-2)（F(0) = 0, F(1) = 1）を求めよ。**
> [参考： ABC318 B - Fibonacci](https://atcoder.jp/contests/abc318/tasks/abc318_b)
<details><summary> 回答　</summary>

```python
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))
```
</details>

### 例題3. 再帰でハノイの塔
**問題: N 枚のハノイの塔を A から C へ移動する手順を出力せよ。**
> [参考： ABC319 C - Hanoi Tower](https://atcoder.jp/contests/abc319/tasks/abc319_c)
<details><summary> 回答　</summary>

```python
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')
```
</details>

### 例題4. 再帰で GCD（最大公約数）を求める
**問題: GCD(A, B) を再帰を使って求めよ。**
> [参考： ABC320 B - GCD with Recursion](https://atcoder.jp/contests/abc320/tasks/abc320_b)
<details><summary> 回答　</summary>

```python
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))
```
</details>