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