c - Fibonacci Computation Time -

is there noticeable computation time difference between recursion-style fibonacci vs. loop-style fibonacci? keep running fibonacci 40 places using recursion , using loop directly afterwards. seems though computation time difference academic.

written in c

recursive solution:

    int main(int argc, const char * argv[]) {     int n, = 0, c;     printf("please enter integer:\n");     scanf("%d", &n);     ( c = 1 ; c <= n ; c++ )     {         printf("%lu ", fibonacci(i));         i++;     }     return 0;     }  long fibonacci(long n) {     if ( n == 0 )         return 0;     else if ( n == 1 )         return 1;     else         return ( fibonacci(n-1) + fibonacci(n-2) ); }; 

for-loop solution:

int main(int argc, const char * argv[]) { int n, first = 0, second = 1, next, c;     printf("please enter integer:\n");     scanf("%d", &n);     ( c = 0 ; c < n ; c++ )     {         if ( c <= 1 )             next = c;         else         {             next = first + second;             first = second;             second = next;         }         printf("%d ",next);     }     return 0; }; 

the conventional recursion method extremely slow compared tail recursive , iterative versions. in example code below iteration version uses unfolded loop along duff's device enter loop. 32 bit unsigned integers, limit fib(47), 64 bit unsigned integers, limit fib(93).

timing done intel 2600k 3.4ghz, xp x64, 64 bit mode. xp or xp x64 high performance counter frequency same cpu clock, 3.4ghz, operating system overhead (like interrupts), affects timing if duration small.

timings fib(40):

fibr() # of microseconds    485468.8 fibt() # of microseconds         0.2 fibi() # of microseconds         0.2 

timing 94 loops, n = 0 93:

fibt() # of microseconds         7 fibi() # of microseconds         5 

example code:

typedef unsigned long long ui64;  ui64 fibr(ui64 n) {     if(n < 2)         return n;     return fibr(n-1) + fibr(n-2); }  // call fibt(n, 0, 1) ui64 fibt(ui64 n, ui64 res, ui64 next) {     if (n == 0)         return res;     return fibt(n - 1, next, res + next); }  ui64 fibi(ui64 n) { ui64 f0, f1, i;     if(n < 2)         return n;     n -= 2;     f1 = f0 = 1;     = 0;     switch(n%8){         do{             f1 += f0;           case 7:             f0 += f1;           case 6:             f1 += f0;           case 5:             f0 += f1;           case 4:             f1 += f0;           case 3:             f0 += f1;           case 2:             f1 += f0;           case 1:             f0 += f1;           case 0:             continue;         }while(n >= (i += 8));     }     return f0; } 

alternate version of fibi(), without n<2 check. f0 , f1 represent changes within loop designed end final sum in f0, initial state of f0 , f1 represent depends if n or odd. if n even, f0 = fib(0) = 0, f1 = fib(-1) = 1, if n odd, f1 = fib(0) = 0, f0 = fib(-1) = 1 . (in case you're curious, fib(-1) = 1, fib(-2) = -1, fib(-3) = 2, fib(-4) = -3, fib(-5) = 5, fib(-6) = -8, ... ).

to explain logic here, n case, fib(-1) = f1 = 1, fib(0) = f0 = 0, fib(1) = (f1 += f0), fib(2) = (f0 += f1), fib(3) = (f1 += f0), fib(4) = (f0 += f1), ... .

ui64 fibi(ui64 n) { ui64 f0, f1, i;     f0 = n & 1;         // if n even, f0=0, f1=1     f1 = 1 - f0;        // else       f1=0, f0=1     = 0;     switch(n%8){         do{             f1 += f0;           case 7:             f0 += f1;           case 6:             f1 += f0;           case 5:             f0 += f1;           case 4:             f1 += f0;           case 3:             f0 += f1;           case 2:             f1 += f0;           case 1:             f0 += f1;           case 0:             continue;         }while(n >= (i += 8));     }     return f0; }