プログラミングの学習で、よくフィボナッチ数列が取り上げられている
イメージがある。それはなぜかと考えてみると、再帰性の考え方を
理解する上で、フィボナッチ数列が有効だからだろう。
そのアルゴリズムの基底部となるのは、最初の数列であるF(0)=0とF(1)=1だけ。
あとはこの2つの基底部を使って、どんな自然数でも構成できる。
フィボナッチ数列は、直前の2つのフィボナッチ数の和が数列として、
どんどん数珠つなぎとなったもののこと。

フィボナッチ数列の定義は、F(n) = F(n-1) + F(n-2)

なので、たとえばn=3を代入してみると、それは

F(3) = F(2) + F(1) …(a)

となって、これはさらに、F(2)が以下のように分解できる。

F(2) = F(1) + F(0)

これを式 …(a)に戻すと、

F(3) = (F(1) + F(0)) + F(1) となるので、このことにより、
F(3) = (1 + 0) + 1 = 2となる。