This is probably one of the most terrible recursive functions you can write because it branches out exponentially. Translation: it is horribly, horribly inefficient. Notice where the function is recursively called twice:
Code:
int f ( int i )
{
if ( i < 1 ) return 0;
if ( i == 1 ) return 1;
return f ( i - 1 ) + f ( i - 2 );
}
This is something you want to avoid, so the fibonacci program is better written iteratively than recursively. But if you must, there is a way to give the recursive function a linear running time by placing the values in an array so that you don't recalculate:
Code:
int fImproved ( int i )
{
static a[BUFSIZ] = {0};
if ( i == 0 || i == 1 )
return a[i] = i;
if ( a[i] == 0 )
return a[i] = fImproved ( i - 1 ) + fImproved( i - 2 );
return a[i];
}
-Prelude