関数が自分自身を呼び出す再帰は、ツリー走査・分割統治・グラフ探索などで威力を発揮する強力な手法です。
日野 こむぎ
再帰って関数が自分を呼ぶの?
なんかループみたい?
藤森 さやか 先生
そうよ、再帰は関数が自分自身を呼び出す書き方なのよ。
「分割統治法」のような解き方と相性がいいの。
青木 澪
代表的な例は階乗計算 factorial(n) = n × factorial(n-1)、フィボナッチ数列、ハノイの塔、ツリーの走査ね。
再帰は「同じ構造の小さな問題に分割」できるときに威力を発揮するわ。
桃井 すみれ
終わらなくなっちゃわないんですかぁ?
青木 澪
いい質問ね。
再帰には必ずベースケース(終了条件)が必要なの。
階乗なら「n=1ならば1を返す」で止まるようにするのよ。
藤森 さやか 先生
終了条件がないと無限再帰してスタックオーバーフローになるわ。
深すぎる再帰もスタックを使い切るから注意ね。
日野 こむぎ
再帰の問題点はある?
青木 澪
同じ計算を何度も繰り返してしまう場合があるの。
フィボナッチ数列を素直に再帰すると指数的に遅くなるわ。
そこで{kw('メモ化', '一度計算した結果をキャッシュして、再計算を避ける手法。
動的計画法の一種')}で計算結果を保存すれば、O(n) に高速化できるのよ。
藤森 さやか 先生
これを発展させたのが動的計画法 (Dynamic Programming, DP) よ。
再帰は大事な発想だけど、実際にはメモ化やDPで効率化することが多いのよ。
桃井 すみれ
なるほどぉ、賢く工夫するんですねぇ♪えへへ、面白いですぅ!
確認クイズ
再帰関数で必ず必要な要素はどれか。
- ループ
- ベースケース (終了条件)
- グローバル変数
- ポインタ
こたえを見る
正解: 2. ベースケース (終了条件)
再帰関数には必ずベースケース (終了条件) が必要です。これがないと無限に自己呼び出しを続け、スタックオーバーフローになります。
