フィボナッチ数列と再帰の重複計算とは？ふぃぼなっちすうれつとさいきのじゅうふくけいさん
フィボナッチ数列と再帰の重複計算とは、直前2項の和が次の項になる数列。定義をそのまま再帰関数にすると同じ引数の計算が何度も繰り返され、項数に対して呼出し回数が指数的に増える。再帰の効率を説明する定番の題材になっている。
最終更新：2026-10-06
応用情報を最短で暗記・合格する →具体例
第40項を素朴な再帰で求めると呼出し回数が数億回に達する。一度計算した値を配列に控えて再利用するか、小さい項から順に足し上げる反復に書き換えると、項数に比例する時間で計算できる。
試験での引っ掛け
「再帰は遅い」のではなく、重複した部分問題を作る書き方が遅い。ハノイの塔のように重複が生じない再帰は、反復に書き直しても計算量は変わらない点を混同しやすい。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。