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  (うっと思うほど、時間がかかるはず)

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) {



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

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

   return 0;
}