hqt

Fibonacci - Recursion compare

hqt
Jul 29th, 2012
162
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 0.79 KB | None | 0 0
  1. #include <time.h>
  2. #include <stdio.h>
  3. #include <time.h>
  4.  
  5. long long fib_r(int n){
  6.     return n<=2?1:fib_r(n-2)+fib_r(n-1);
  7. }
  8.  
  9. long long fib(int n){
  10.     long long series[32000];
  11.     int i=0;
  12.     series[1] = 1;
  13.     series[2] = 1;
  14.     for(i=3; i<=n; i++){
  15.         series[i] = series[i-1] + series[i-2];
  16.     }
  17.     return series[n];
  18. }
  19. void main() {
  20.    
  21.     time_t before;
  22.     time_t after;
  23.     int n = 45;
  24.    
  25.     /* first test */
  26.     time(&before);
  27.     long long res1 = fib_r(n);
  28.     time(&after);
  29.     printf("%lld\n",res1);
  30.     printf("Total recursion time : %d\n",after - before);
  31.    
  32.     /* second test */
  33.     n = 30000;
  34.     time(&before);
  35.     long long res2 = fib(n);
  36.     time(&after);    
  37.     printf("%lld\n",res2);
  38.     printf("Total normal time: %d\n", after - before);
  39. }
Advertisement
Add Comment
Please, Sign In to add comment