「課題のプログラムを実行するときに，fib(40)は何回呼び出しますか? fib(39)は何回呼び出しますか? …というように，引数ごとにfibの呼び出し回数を分けると，どうなるでしょうね?」
関数の呼び出し回数 - わさっき
(略)
「さっき言った，fibの各引数を何回呼び出すかってのを，fibに与える初期値ごとに求めると，面白い性質が出てくるんだけどね」
「えっとどういうことでしょうか?」
「2重ループを作ってください」
求めてみました．Cのコードがちょっと楽しかったのですが，諸事情によりC版は公開せず，Rubyでワンライナーを作りました．
まずはフィボナッチ数を求めるところから．
$ ruby -e 'def fib(n) n<=2?1:fib(n-1)+fib(n-2) end;puts fib(40)'
しばらく待っても，答えが返ってきません*1．数値を減らします．
$ ruby -e 'def fib(n) n<=2?1:fib(n-1)+fib(n-2) end;puts fib(20)'
6765
$ ruby -e 'def fib(n) n<=2?1:fib(n-1)+fib(n-2) end;puts fib(30)'
832040
そうしていると，fib(40)の結果も出ました．102334155で，Cのと同じです．
小さいのから順に，フィボナッチ数を出力させましょう．
$ ruby -e 'def fib(n) n<=2?1:fib(n-1)+fib(n-2) end;1.upto(20){|i|puts fib(i)}'
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040
『fibの各引数を何回呼び出すかってのを，fibに与える初期値ごとに求める』ための処理を，付け加えます．
$ ruby -e 'def fib(n,a) a[n-1]+=1;n<=2?1:fib(n-1,a)+fib(n-2,a) end;1.upto(30){|i|a=[0]*i;puts fib(i,a);a.size.times{|j|puts " fib(#{j+1}):#{a[j]}"}}'
メソッドfibを2引数にしました．fibの第1引数は1オリジン，配列aは0オリジンです．
出力は長くなるので，fib(30)の呼び出し分だけを．
832040 fib(1):317811 fib(2):514229 fib(3):317811 fib(4):196418 fib(5):121393 fib(6):75025 fib(7):46368 fib(8):28657 fib(9):17711 fib(10):10946 fib(11):6765 fib(12):4181 fib(13):2584 fib(14):1597 fib(15):987 fib(16):610 fib(17):377 fib(18):233 fib(19):144 fib(20):89 fib(21):55 fib(22):34 fib(23):21 fib(24):13 fib(25):8 fib(26):5 fib(27):3 fib(28):2 fib(29):1 fib(30):1
最終行の「fib(30):1」は，最初のワンライナーでfib(30)を計算する際，fib(30)はちょうど1回呼び出したことを表します．その20行前の「fib(10):10946」は，fib(30)を計算するためにfib(10)をその回数呼び出したということです．
他の値も見ると，x≧2のとき，fib(x)を計算する際の「fib(x)の呼び出し回数」「fib(x-1)の呼び出し回数」「fib(x-2)の呼び出し回数」…「fib(2)の呼び出し回数」がフィボナッチ数になっていることが分かります．fib(1)の呼び出し回数は，fib(3)のそれと一致します．
さらに，「fib(1)の呼び出し回数」と「fib(2)の呼び出し回数」の和は，fib(x)と等しくなります．これは，fib(x)を求めるにあたり「+1」されるのが，fib(1)かfib(2)を呼び出したときに限られるからですね．
*1:Rubyらしいコードで，かつ効率良く計算するなら，フィボナッチ数列、今日も - rubyco（るびこ）の日記ですね．
