#author("2026-06-24T10:11:08+09:00;2023-02-23T23:33:35+09:00","default:vip","vip") #author("2026-06-24T10:15:02+09:00;2023-02-23T23:33:35+09:00","default:vip","vip") *[[練習問題]]の回答例 [#md82ea7f] #ls2(,compact) ---- * フィボナッチ数列 課題3 [#fib3] -再帰版の利点: フィボナッチ数列の定義を直接に表現でき、読み書きに優れる。（この性質はこの問題に限らず、難問でも自然に思いつきやすい。） -再帰版の欠点: 素朴な実装では同じ値を何度も計算するため計算量が指数的増加 O(1.618^n) となり、大きいフィボナッチ数の算出は文字通り桁違いに遅くなる（これは問題依存。再帰が常に爆発的計算量というわけではない）。なのでメモ化しよう！~ :再帰版の利点|フィボナッチ数列の定義を直接に表現でき、読み書きに優れる。（この性質はこの問題に限らず、難問でも自然に思いつきやすい。） :再帰版の欠点|素朴な実装では同じ値を何度も計算するため計算量が指数的増加 O(1.618^n) となり、大きいフィボナッチ数の算出は文字通り桁違いに遅くなる（これは問題依存。再帰が常に爆発的計算量というわけではない）。なのでメモ化しよう！~ また再帰が深くなるとコールスタックが溢れて関数呼び出し限界を迎えて異常停止する。関数呼び出し自体もオーバーヘッドがあり若干のコストだ。 -反復版： 途中結果を保持しながら順に計算するため計算量が線形 O(n) で高速。スタックオーバーフローの心配もない。ただし、数列の定義との対応は再帰版ほど直感的でない。 :反復版|途中結果を保持しながら順に計算するため計算量が線形 O(n) で高速。スタックオーバーフローの心配もない。ただし、数列の定義との対応は再帰版ほど直感的でない。