後半：Pythonで「使える」再帰アルゴリズムを身につける
前半で、再帰の感覚とコールスタックのイメージはだいぶつかめてきたと思う。
後半では、もう一歩踏み込んで「典型パターン」と「考え方の型」を、Pythonコードでしっかり体に入れていこう。
階乗 factorial で再帰の型を固める
階乗の定義と再帰のつながり
階乗（factorial）は、数学では次のように定義される。
0! は 1
n! は n × (n-1)!（n > 0 のとき）
この「自分自身を使って自分を定義している」形が、そのまま再帰関数の形になる。
再帰が一番きれいにハマる典型例だ。
Pythonでの階乗の再帰実装
def factorial(n: int) -> int:
if n == 0: # ベースケース
return 1
return n * factorial(n - 1) # 再帰ステップ
print(factorial(5)) # 120
ここで重要なのは、数学の定義とコードがほぼ一対一で対応していること。
0! を 1 と決める部分がベースケースで、n! を n × (n-1)! と書く部分が再帰ステップになっている。
この「数学の再帰的な定義を、そのままコードに写す」という感覚が身につくと、アルゴリズムの本や解説を読んだときに「これ、Pythonでそのまま書けるな」と見えるようになる。
フィボナッチ数列と「やりすぎ再帰」の罠
フィボナッチ数列の再帰定義
フィボナッチ数列は、次のように定義される。
fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)（n ≥ 2）
これも、定義そのものが再帰になっているパターンだ。
Pythonでの素直な再帰実装
def fib(n: int) -> int:
if n == 0: # ベースケース1
return 0
if n == 1: # ベースケース2
return 1
return fib(n - 1) + fib(n - 2) # 再帰ステップ
print(fib(6)) # 8
見た目はとても美しい。
定義とコードがほぼ同じで、「アルゴリズムをそのまま書いた」感じになっている。
パフォーマンスを深掘りする
ここが重要ポイントだ。
この実装は、n が大きくなると一気に遅くなる。
理由は、「同じ値を何度も何度も計算している」からだ。
例えば fib(6) を計算するとき、fib(5) と fib(4) を呼び、fib(5) は fib(4) と fib(3) を呼ぶ。
すると fib(4) や fib(3) が何度も再計算されることになる。
アルゴリズムの言葉で言えば、時間計算量が指数関数的に増える。
セキュリティ・運用の視点から見ると、「少し大きな入力を与えただけでCPUを食い尽くす」ようなコードは、サービス妨害（DoS）的な弱点になり得る。
ここで学んでほしいのは、「再帰で書ける＝良いアルゴリズム」ではないということ。
再帰は表現方法であって、「速さ」「メモリ」「安全性」は別軸でちゃんと評価する必要がある。
リストと文字列を再帰で扱う
リストの合計を再帰で求める
前半で軽く触れたリストの合計を、もう少し意識して眺めてみよう。
def sum_list(nums: list[int], i: int = 0) -> int:
if i == len(nums): # ベースケース：末尾まで来たら 0
return 0
return nums[i] + sum_list(nums, i + 1)
print(sum_list([1, 2, 3, 4])) # 10
ここでやっていることは、とてもシンプルだ。
リストの末尾まで来たら合計は 0 とみなす。
そうでなければ、「今の要素」＋「残りの要素の合計」として、問題を一歩だけ小さくしている。
この「今の1つ＋残りを再帰に任せる」というパターンは、リスト・タプル・文字列など、シーケンス型を再帰で扱うときの基本形になる。
文字列を逆順にする再帰
次は文字列を逆順にする例を見てみよう。
例えば “abcd” を “dcba” にしたい、という問題だ。
def reverse(s: str) -> str:
if s == "": # ベースケース：空文字列
return ""
return reverse(s[1:]) + s[0]
print(reverse("abcd")) # dcba
考え方はこうだ。
文字列 s を逆順にしたいとき、「先頭以外を逆順にしたもの」の末尾に「先頭の1文字」をくっつければよい。
つまり、「残りを再帰に任せて、最後に自分の分を足す」という構造になっている。
ここでも、「先頭」と「残り」に分けるという分解の仕方が出てきている。
配列でも文字列でも、「先頭＋残り」という分解は再帰の鉄板パターンだ。
ネストした構造と再帰：Pythonらしい本番の出番
ネストしたリストをたどる再帰
Pythonでは、リストの中にリストが入っているような「ネスト構造」を扱うことがよくある。
例えば、次のようなデータだ。
data = [1, [2, 3], [4, [5, 6]], 7]
この中にある数値をすべて合計したいとする。
ネストの深さがバラバラなので、単純な for 文だけではきつい。
ここで再帰が本領発揮する。
def sum_nested(x) -> int:
if isinstance(x, int): # ベースケース：整数ならそのまま返す
return x
total = 0
for item in x: # リストだと仮定して、要素を順に処理
total += sum_nested(item) # 要素がリストでも整数でも、再帰に任せる
return total
data = [1, [2, 3], [4, [5, 6]], 7]
print(sum_nested(data)) # 28
ここでのポイントは、「型によってベースケースを変える」という発想だ。
整数ならそれ以上分解できないので、そのまま返す。
リストなら中身を順に見て、要素に対して同じ処理を再帰的に行う。
このパターンは、JSON風のデータや設定ファイル、ツリー構造などを扱うときに非常によく出てくる。
再帰とループ、どちらを選ぶべきか
思考としての再帰、実装としてのループ
実務寄りの話をすると、「頭の中では再帰で考えて、コードとしてはループで書く」ことがよくある。
理由は、ループの方が次のような点で有利だからだ。
スタックオーバーフロー（RecursionError）の心配がない
パフォーマンスが安定しやすい
Pythonインタプリタの最適化が効きやすい
ただし、木構造やネスト構造、再帰的な数学的定義をそのまま表現したいときは、再帰の方が圧倒的に読みやすいことも多い。
「読みやすさ」と「安全性・速さ」のバランスをどう取るかが、プロの判断ポイントになる。
セキュリティ・パフォーマンスの視点
入力サイズがどこまで大きくなり得るか。
最悪ケースで再帰の深さはどれくらいか。
同じ計算を何度も繰り返していないか。
このあたりをざっくりでもいいので意識しておくと、「とりあえず動くコード」から一段レベルアップできる。
特に、ユーザー入力や外部データをそのまま再帰の深さに反映させるようなコードは、セキュリティ的にも慎重に設計した方がいい。
再帰を書くときの「思考の型」
先にベースケースを決める
再帰を書くときは、まず「どんな状態になったら、もう再帰をやめていいか」を決める。
ここを先に決めることで、「必ず終わる」ことが保証される。
n が 0 になったら終わり。
リストの末尾まで来たら終わり。
空文字列になったら終わり。
整数にたどり着いたら終わり。
この「終点」を先に決める癖は、バグ防止にもセキュリティにも効く。
問題を「一歩だけ」小さくする
次に、「今の問題を一歩だけ小さくする」ことを考える。
n! を「n × (n-1)!」にする。
リスト全体の合計を「今の要素＋残りの合計」にする。
文字列全体の逆順を「残りの逆順＋先頭」にする。
ネスト構造全体の処理を「今の要素＋残りの要素の処理」にする。
ここで大事なのは、「自分で全部やろうとしない」ことだ。
自分は一歩だけ進めて、残りは再帰呼び出しに任せる、というマインドセットが再帰のコアにある。
スタックの深さと計算量をざっくり見積もる
最後に、「この再帰はどれくらい深くなるか」「呼び出し回数はどれくらいか」をざっくりでいいのでイメージする。
深さが n で、呼び出し回数もだいたい n なら、まだわかりやすい。
フィボナッチのように、呼び出し回数が指数関数的に増えるものは要注意だ。
この「最悪ケースをざっくり想像する」癖は、アルゴリズム設計とセキュリティ設計の両方で効いてくる。
まとめ：再帰は「問題分解の筋トレ」
ここまでで、Python におけるアルゴリズムと再帰関数を、かなり実戦寄りに見てきた。
再帰は「自分自身を呼ぶ関数」だけれど、本質は「大きな問題を同じ形の小さな問題に分解する技術」だということ。
ベースケースと再帰ステップを先に設計することで、「必ず終わる」「読みやすい」再帰になること。
階乗・フィボナッチ・リスト・文字列・ネスト構造など、典型パターンを通して再帰の型を体に入れられること。
再帰は美しいが、最大再帰深度や計算量、データコピーのコストには常に注意が必要なこと。
