recursion とは何ですか？

Question

recursion とは何ですか？

Accepted Answer

**Recursion** は、function が同じ問題の小さい version を解くために自分自身を呼ぶことです。すべての recursion には止めるための **base case** と、base に近づく **recursive case** が必要です。

## 考え方

問題を同じ形の smaller subproblems に分解します。各 call は **call stack** に frame を push し、return で pop されます。

## 例

```python
def factorial(n):
    if n <= 1:            # base case: stop recursing
        return 1
    return n * factorial(n - 1)   # recursive case: smaller problem

factorial(4)             # 4 * 3 * 2 * 1 -> 24
```

## Trace

```text
factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * 3 * 2 * 1 = 24
```

## Complexity

この例では **O(n)** time と **O(n)** stack space（call ごとに 1 frame）です。

## pitfalls

- **base case がない** -> infinite recursion -> stack overflow。
- deep recursion は stack を使い切る可能性があります。tail-call optimization がない language もあります。
- overlapping subproblems を recompute すると exponential time になり得ます（memoization で修正）。

## なぜ重要なのか

recursion は trees、graphs、divide and conquer のような self-similar problem を loop より自然に表現します。merge sort、backtracking、dynamic programming の mental model でもあります。call stack を理解すると debugging と memory reasoning も良くなります。