再帰とは
再帰（recursion）とは、関数が自分自身を呼び出す仕組みです。繰り返しを使って書けるものは再帰でも書けますが、問題によっては再帰の方が自然に記述できます。
再帰の基本構造
再帰関数には必ず以下の2つが必要です:
- 基底ケース（base case）: これ以上再帰しない終了条件
- 再帰ケース（recursive case）: 自分自身を呼び出す部分
python
def factorial(n): """n! を再帰で求める""" if n == 0: # 基底ケース return 1 return n * factorial(n - 1) # 再帰ケースfactorial(5) # 5 * 4 * 3 * 2 * 1 = 120呼び出しの流れ:
factorial(5)→5 * factorial(4)factorial(4)→4 * factorial(3)factorial(3)→3 * factorial(2)factorial(2)→2 * factorial(1)factorial(1)→1 * factorial(0)factorial(0)→1（基底ケース）
代表的な再帰の例
フィボナッチ数列
python
def fib(n): """フィボナッチ数列のn番目を返す""" if n <= 1: # 基底ケース return n return fib(n-1) + fib(n-2) # 再帰ケースfib(0) # 0fib(1) # 1fib(6) # 8注意: 上の実装は同じ計算を何度も繰り返すため、
nが大きいと非常に遅くなります。メモ化で改善できます。
二分探索（再帰版）
python
def binary_search(lst, target, low=0, high=None): """ソート済みリストから target を二分探索する""" if high is None: high = len(lst) - 1 if low > high: # 基底ケース（見つからない） return -1 mid = (low + high) // 2 if lst[mid] == target: # 基底ケース（見つかった） return mid elif lst[mid] < target: return binary_search(lst, target, mid + 1, high) else: return binary_search(lst, target, low, mid - 1)nums = [1, 3, 5, 7, 9, 11, 13, 15]binary_search(nums, 7) # 3（インデックス）binary_search(nums, 10) # -1（見つからない）ハノイの塔
python
def hanoi(n, from_peg, to_peg, via_peg): """n枚の円盤を from_peg から to_peg に移動する""" if n == 1: print(f"円盤1を {from_peg} から {to_peg} に移動") return # n-1枚を via_peg に移動 hanoi(n - 1, from_peg, via_peg, to_peg) # n枚目を to_peg に移動 print(f"円盤{n}を {from_peg} から {to_peg} に移動") # n-1枚を to_peg に移動 hanoi(n - 1, via_peg, to_peg, from_peg)hanoi(3, "A", "C", "B")木構造の探索
python
# 木をネストした辞書で表現tree = { "value": 1, "children": [ { "value": 2, "children": [ {"value": 4, "children": []}, {"value": 5, "children": []}, ] }, { "value": 3, "children": [ {"value": 6, "children": []} ] } ]}def tree_sum(node): """木の全ノードの値の合計を返す""" total = node["value"] for child in node["children"]: total += tree_sum(child) # 再帰 return totaltree_sum(tree) # 1+2+3+4+5+6 = 21再帰の深さ制限
Pythonでは再帰の深さに制限があります（デフォルト1000）。
python
import syssys.getrecursionlimit() # 1000# 制限を変更（注意が必要）sys.setrecursionlimit(5000)練習: 再帰で冪乗
再帰を使って base の exp 乗を計算する関数 power(base, exp) を定義してください（exp >= 0）。
練習: 再帰でリスト合計
再帰を使ってリストの全要素の合計を求める関数 recursive_sum(lst) を定義してください。