フィボナッチ数を求める実装

www.geeksforgeeks.org

　ここを見ていたのですが、Method 5の再帰が最初みていまいちわからなかったです。Method4のoptimizedということでトリッキー度が増しているんでしょうけどもpower関数の処理の大部分multipy以降を呼ばすに自分を呼び出しているのが奇異にみえました。

/* Optimized version of power() in method 4 */
void power(int F[2][2], int n) 
{ 
  if( n == 0 || n == 1) 
      return; 
  int M[2][2] = {{1,1},{1,0}}; 
  
  power(F, n/2); 
  multiply(F, F); 
  
  if (n%2 != 0) 
     multiply(F, M); 
} 

　これの呼び出しを追ってみると、たしかにうまいこといってます。再帰を変数nの数列作成とそのスタックのために使っているように理解しました。
　再帰を使わずループにしても効率とか読みやすさとか変わらないと最初思ったのですが、このループでできる数列を関数的に作るのが意外に難しいと感じました*1。若番から数列を作ろうとしても同じ数字から分岐が必要なのでアルゴリズムをすぐには思いつきません。int型の2で割ったとき(ビットシフトしたとき)の切り捨て仕様にフィットして、スタック領域を数列のそれに当てはめて先入れ先出しの動作でmultipyの呼び出しにつなげています。むーん。

入力n	multipyで呼ばれるときのn
3	2
4	3
5	2,4
6	2,5
7	3,6
8	3,7
9	2,4,8
10	2,5,9
11	2,5,10
12	2,5,11
13	3,6,12
14	3,6,13
15	3,7,14
16	3,7,15

にしても、フィボナッチ数列は0始まりか1始まりかどちらがより説明においていいのかはよくわかりません。0からだと次の数値との比がでないので1のほうが語りやすい気がします。