1つ前の数と2つ前の数を足せば次の数が出てくることから、次のように計算すればいいことがわかるでしょう。2);こうして、次のようなコードで求められることがわかります。値を入力すれば、手で計算したときと同じ結果が得られることがわかるでしょう。2つの結果を使っている点が異なっています。【広告】プログラマの数学第2版プログラミングや数学に関心のある読者を対象に、プログラミング上達に役立つ「数学の考え方」をわかりやすく解説しています。数学的な知識を前提とせず、たくさんの図とパズルを通して、平易な文章で解き明かしています。入力する値を1ずつ増やしていくと、あるところからもっさりとした動きになることがわかります。実は、このコードでは、計算量がすごいことになっています。関数が何回呼び出されたかを表示するために次のようにコードを書き換えてみてみます。入力すると、3億回程度も呼び出されていることがわかります。40番目の値を計算するだけなのに、どうしてこんなことになるのでしょうか。2つの結果を使っている点が異なっている」と書きましたが、この点が原因です。このせいで同じような計算を何度もしていることになります。これを理解するには、どのように関数が呼び出されているかを見てみるのがいいでしょう。5を入力した場合を考えましょう。すると、4番目と3番目の和を返そうとします。4番目は、3番目と2番目の和、3番目は2番目と1番目の和、というようにどんどんさかのぼっていきます。して4番目が計算できたら、今度は3番目を同じように計算し、その和が5番目の数になる、という流れです。表すことにすると、次のような計算をしていることになります。分解して計算するのは無駄です。一度値がわかってしまえば、今後はその値を使えばよく、再帰させる意味はありません。これをやっていなかったために、呼び出し回数がすごいことになっていたのです。番目の数字を格納する配列を使うように変えてみます。初期化し、0番目と1番目の値を設定します。格納し、計算済みなら再利用するようにしています。これにより、計算回数は激減します。このように、途中の計算結果を配列に格納しておいて、必要ならそれを使いまわす、というテクニックを競プロではよく使います。いい、メモ化を使った再帰をメモ化再帰といいます。絵で見てわかる26のアルゴリズム本書は、アルゴリズムを独学する人のために作りました。学ぶときにはイメージしやすく、復習するときには思い出しやすくなるよう、基本的な26のアルゴリズム+7つのデータ構造をすべてイラストにしています。番目からさかのぼって値を求めていくことで計算しました。その際、一度さかのぼって判明した値は、その後の計算で使いまわすことで計算量が減らせることを見ました。これを見て、「そもそも前から順番に求めていけば楽じゃね?」と思う人もいるでしょう。番目の値を求めるには、前から求めていく方が速くて、しかも、わかりやすいです。0;}今の場合は、漸化式が与えられているので、このように書くほうが自然に感じられるでしょう。問題によっては、手前にさかのぼっていくコードは思いつきやすいけど、前から順番に求めていくコードは思いつきにくい、というものもあります。そのため、どちらの考え方もマスターしておく方がいいでしょう。トップダウンで計算したときに使ったメモ化再帰も、ここで見たボトムアップでの計算も、動的計画法の一種です。動的計画法は、競プロではいろんな形で出題されます。