#include <stdio.h>//第1講演習 5
#include <time.h>
#include <stdlib.h>

int fibosaiki(int n){
	if(n<=1) return 1;
	else{
		return fibosaiki(n-1)+fibosaiki(n-2);
	}
}
int fibo(int n){
	int i,a,b,f;
	if(n<=1)return 1;
	else{
		for(i=2,a=1,b=1;i<=n;i++){
			f=a+b;
			b=a;
			a=f;
		}
		return f;
	}
}
int main() {
	int x,y,n;
	clock_t ti[3];
	n=41;
	ti[0]=clock();//1回目時刻
	x=fibosaiki(n);//再帰あり
	ti[1]=clock();//2回目時刻
	y=fibo(n);//再帰なし
	ti[2]=clock();//3回目時刻
	printf("再帰フィボナッチ(%d)=%d,時間＝%d\n",n,x,ti[1]-ti[0]);
	printf("再帰なしフィボナッチ(%d)=%d,時間＝%d\n",n,y,ti[2]-ti[1]);
	
	printf("1回目時刻＝%d\n2回目時刻＝%d\n3回目時刻＝%d\n",ti[0],ti[1],ti[2]);
	//再帰なしの方が短時間で結果を求められる
	//ｎが小さいと時間が0になるのでn=40ぐらいが差を見つけられる
	return 0;
}