末尾再帰最適化

はじめに

「フィボナッチ数列」を題材に末尾再帰最適化の効果を解説します。

前提知識

末尾再帰最適化の効果を評価する指標として、計算量とオーダー記法を用います。コンピュータ科学の世界では、アルゴリズムの効率を評価するために「計算量」という概念が頻繁に使用されます。

計算量とは

計算量は、ある処理を行うために必要なリソースの量を示す指標で、時間計算量と空間計算量の2つの主要な種類があります。時間計算量は、アルゴリズムが問題を解決するために必要な計算ステップの数を示します。一方、空間計算量は、アルゴリズムが問題を解決するために必要なメモリの量を示します。計算量を表現するために広く使用される記法が「オーダー記法」です。

オーダー記法とは

計算量を表現するために広く使用される記法が「オーダー記法」です。オーダー記法は、アルゴリズムの計算量を表現するための記号で、データ量がnであったとき、どれくらいの計算が必要になるかを示します。

本題

フィボナッチ数列の漸化式

F_0 = 0
<br>
F_1 = 1
<br>
F_n+2 = F_n + F_n+1 (n ≧ 0)