再帰

定義

関数や手続きが自分自身を呼び出す処理構造。分割統治の基礎。

詳細解説

問題を同種のより小さな部分問題に分解して解く手法で、終了条件（ベースケース）と再帰呼出し（再帰ステップ）の2要素から成る。階乗 n! = n×(n−1)! 、フィボナッチ、二分探索、クイックソート、マージソート、木構造の走査等に利用される。スタックを使った繰返し（ループ）に変換可能で、深い再帰はスタックオーバフローを招く。末尾再帰最適化を行う言語ではループと同等の効率になる。メモ化や動的計画法と組み合わせて重複計算を回避できる。

「再帰」が出る問題

• スタックの動作原理として、正しいものはどれか。

• 動的計画法の特徴として、正しいものはどれか。

• RNN（再帰型ニューラルネットワーク）が得意とする処理はどれか。

関連用語

よくある質問