STEP 10.1　フィボナッチ数　(fibonacci number)

<問題> フィボナッチ数は、以下の漸化式で定義される。

 F (0) = 0,  F (1) = 1
 F (N) = F (N -1) +  F (N - 2) (N > 1)

フィボナッチ数を求める再帰プログラムを作成せよ　（定番のプログラム例題です）

<実行結果 例>　
n :7
fib (7) = 13

n :10
fib (10) = 55

n :45 
fib (45) = 1134903170  (うっと思うほど、時間がかかるはず）


解答プログラムの下に、Windows での計測用プログラムあり

UNIXで実行できる場合は、解答プログラムの上のものを、timeコマンドで実行してみるとよい

実行ファイルをfibとするとき
time fib
n :45
fib (45) = 1134903170

real 0m32.773s 　(コマンド起動から終了までの時間。下のユーザCPU時間のほか、入出力の時間なども加算)
user 0m30.665s　（ユーザのコマンドがCPUを使用した時間) （←ここに注目)
sys 0m0.007s (このコマンドにコマンド以外のシステム(OS)関係の処理が要した時間)

こちらの実行結果が出るかもしれません

time fib
n :45
fib (45) = 1134903170
9.615u 0.000s 0:10.77 89.2% 0+0k 0+0io 0pf+0w

コマンド起動から終了までに10.77秒　userに9.615 sysに0秒。


解答例
#include <stdio.h>

int fib(int n);


int fib(int n) {
   if (n == 0)
      return 0;
   else if (n == 1)
      return 1;
   else
      return fib(n-1) + fib(n-2);
}


int main (void) {
   int n;
   printf ("n :");
   scanf ("%d", &n);

   printf("fib (%d) = %d \n", n, fib(n));

   return 0;
}



/* WINDOWSの場合の計測用プログラム clでコンパイル確認してあります。 gccは不可 */

#include <stdio.h>
#include <Windows.h>

int fib(int n);

int fib(int n) {
   if (n == 0)
      return 0;
   else if (n == 1)
      return 1;
   else
      return fib(n-1) + fib(n-2);
}


int main(void) {
   _int64 startTime; /* 開始時間 PC起動からの経過時間 */
   _int64 elapsedTime; /* 停止時間(経過後の時間) */

   int n;
   printf ("n :");
   scanf ("%d", &n);

   printf("-- start -- \n");
   startTime = GetTickCount(); /* システム時間 */
   
   printf("fib (%d) = %d \n", n, fib(n));
      
   elapsedTime = GetTickCount(); /* 時間 */
   printf("-- stop -- \n");

   printf("elapsed time = %d ms \n", elapsedTime - startTime); /* 減算 */

   return 0;
}