Compare RecursiveP with DynamicP

/*

https://jaeonysos.tistory.com

Compare RecursiveP with DynamicP

Writer : Mun Jae In

Date : 2017.12.16

*/

#include <stdio.h>

#include <time.h>

long long Fibonacci_dynamic(int n);

long long Fibonacci_recur(int n);

long long m[40]={0};

int main(int argc, char * argv[])

{

clock_t t1,t2;

int n;

m[1] = 1;

m[2] = 2;

for(n=20 ; n<=40; n++){

t1 = clock();

printf("Fib(%d) = %lld \n",n,Fibonacci_dynamic(n));

t1 = clock() - t1;

printf("Dynamic 수행시간 : %f seconds.\n\n",((float)t1)/CLOCKS_PER_SEC);

t2 = clock();

printf("Fib(%d) = %lld \n",n,Fibonacci_recur(n));

t2 = clock() - t2;

printf("Recursive 수행시간 : %f seconds.\n\n",((float)t2)/CLOCKS_PER_SEC);

}

return 0;

}

long long Fibonacci_dynamic(int n)

{

if(n<0)

return 0;

if(m[n] == 0)

{

m[n] = Fibonacci_dynamic(n-1) + Fibonacci_dynamic(n-2);

}

return m[n];

}

long long Fibonacci_recur(int n)

{

if(n==1)

return 1;

else if(n==2)

return 2;

else return Fibonacci_recur(n-1) + Fibonacci_recur(n-2);

}