[Ruby] 再帰関数のメモ化をしてみる

フィボナッチ数列を例に、再帰関数のメモ化を実装して行きたいと思います。

ベンチマークもとって、速度を比較して行きます。

ベタに実装

メモ化を使わずに実装します。

 

この実装だと、40項を計算するあたりから、速度が急激に遅くなって行きます。

以下、ベンチマークとった結果です。

やはり遅い。。。

 

メモ化

一度計算した結果は、配列に保存しておくことで無駄な計算をしなくても済みます。

 

以下、ベンチマークをとった結果です。

 

再帰関数使わずにできる

 

面白い!

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA