question about fibonacci and recusive exponenets

[Terabojin]

So, why does recursive exponentiation crash the stack but recursive Fibonacii doesn't?  I mean doesn't Fibonacci call it's self many more times than integerPower?  And since Fibonacii doesn't crash why does it get slower and slower?

 

 

[Andre S. Veteran]

Could you show us your implementation and how you're calling it?

[Terabojin]

This is the code that i'm using for the Fibonacci :

#include <stdio.h>
//recursive fibonacci function

unsigned long long int fibonacci(unsigned int n); //function prototype
int count = 0;

//function main begins program execution

int main(void)
{
	unsigned long long int result; //fibonacci value
	unsigned int number; //number input by user
	count++;

	//obtain integer from user
	printf("%s", "Enter an integer: \n");
	scanf("%u", &number);

	//calculate fibonacci value for number input by user
	result = fibonacci(number);

	//display result
	printf("Fibonacci( %u ) = %11u\n", number, result);
} //end main

//recursive definition of function fibonacci
unsigned long long int fibonacci( unsigned int n)
{
	//base case
	if ( 0 == n || 1 == n){
		return n;
	} //end if
	else{ //recursive step
		return fibonacci ( n - 1) + fibonacci ( n - 2 );
	} //end else
} //end function fibonacci

[Andre S. Veteran]

I'm not sure where you got the idea that your program doesn't blow the stack. Simply enter 10000 or such large number and watch it crumble to pieces. Any recursive algorithm implemented in C will blow the stack after a certain recursion depth is attained.

 

This is why recursion in C is typically never used, or used only for algorithms that demonstrably do not recurse very deeply, e.g. O(log N) algorithms, because C has no notion of tail recursion.

[Karl L.]

Recursion can be extremely beneficial when used properly, but like Asik noted, deep recursion is almost universally considered to be a bad thing. Some programming languages, like Python and Java, have built-in protections against programs locking up by blowing the stack, but C assumes that you - as the programmer - always know what you are doing. This assumption allows C compilers to optimize for speed by dutifully omitting any such runtime checks as superfluous.

 

To answer your question explicitly, it is likely that your compiler is doing some optimizations to speed up your program that significantly reduce the amount of recursion involved, hence the longer runtime without crashing or freezing. Since the fibonacci() function in particular is fairly trivial (from the compiler's point of view), it is should, likewise, be trivial for the compiler to optimize.

 

Another factor which may affect the run time of your program is the precision of the type that fibonacci() returns. If the user enters a large number (like the 10000 Asik suggested), your program will quickly overflow the precision of unsigned long long int. This overflow ventures into the realm of undefined behavior in C, so it may very well crash your program (or have other, more subtle side-effects, the least of which is the incorrect result the function will return).

 

To demonstrate the effects of compiler optimizations, I modified your program slightly to accept the input number as a command-line argument, compiled it once with optimizations turned off and once with the highest level of optimization, then timed each version. The results speak for themselves. To further demonstrate the negative performance impact of recursion, I wrote an optimized version of the Fibonacci calculation function and timed that version of the program as well. Both programs and their results are below.

// fibonacci-recursive.c

#include <stdio.h>

unsigned long long int fibonacci( unsigned int n )
{
    if ( n == 0 || n == 1 )
    {
        return n;
    }
    else
    {
        return fibonacci( n - 1 ) + fibonacci( n - 2 );
    }
}

int main( int argc, char * argv[] )
{
    unsigned long long int result; // fibonacci value
    unsigned int number = 0; // number input by user
    
    // obtain integer from user
    if( argc > 1 )
    {
        if( sscanf( argv[argc - 1], "%u", &number ) != 1 )
        {
            fprintf( stderr, "Invalid argument: %s\n", argv[argc - 1] );
            number = 0;
        }
    }
    if( !number )
    {
        printf( "%s", "Enter an integer: " );
        scanf( "%u", &number );
    }
    
    // calculate fibonacci value for number input by user
    result = fibonacci( number );
    
    // display result
    printf( "Fibonacci( %u ) = %11u\n", number, result );
    
    return 0;
}

// fibonacci-fast.c

#include <stdio.h>

unsigned long long int fibonacci( unsigned int n )
{
    unsigned long long int n1 = 1; // fibonacci( n - 1 )
    unsigned long long int n2 = 0; // fibonacci( n - 2 )
    unsigned long long int t; // temporary swap value
    
    if( n == 0 || n == 1 ) return n;
    for( unsigned int i = 2; i <= n; i++ )
    {
        t = n1;
        n1 = n2 + t;
        n2 = t;
    }
    
    return n1;
}

int main( int argc, char * argv[] )
{
    unsigned long long int result; // fibonacci value
    unsigned int number = 0; // number input by user
    
    // obtain integer from user
    if( argc > 1 )
    {
        if( sscanf( argv[argc - 1], "%u", &number ) != 1 )
        {
            fprintf( stderr, "Invalid argument: %s\n", argv[argc - 1] );
            number = 0;
        }
    }
    if( !number )
    {
        printf( "%s", "Enter an integer: " );
        scanf( "%u", &number );
    }
    
    // calculate fibonacci value for number input by the user
    result = fibonacci( number );
    
    // display result
    printf( "Fibonacci( %u ) = %11u\n", number, result );
    
    return 0;
}

$ gcc -x c -std=c99 -O0 -o fibonacci fibonacci-recursive.c 
$ time ./fibonacci 7
Fibonacci( 7 ) =          13

real	0m0.002s
user	0m0.000s
sys	0m0.000s
$ time ./fibonacci 27
Fibonacci( 27 ) =      196418

real	0m0.006s
user	0m0.004s
sys	0m0.000s
$ time ./fibonacci 47
Fibonacci( 47 ) =  2971215073

real	0m34.901s
user	0m34.828s
sys	0m0.056s
$ gcc -x c -std=c99 -O3 -o fibonacci fibonacci-recursive.c 
$ time ./fibonacci 7
Fibonacci( 7 ) =          13

real	0m0.002s
user	0m0.000s
sys	0m0.000s
$ time ./fibonacci 27
Fibonacci( 27 ) =      196418

real	0m0.004s
user	0m0.000s
sys	0m0.000s
$ time ./fibonacci 47
Fibonacci( 47 ) =  2971215073

real	0m13.399s
user	0m13.352s
sys	0m0.044s
$ gcc -x c -std=c99 -O0 -o fibonacci fibonacci-fast.c 
$ time ./fibonacci 7
Fibonacci( 7 ) =          13

real	0m0.002s
user	0m0.000s
sys	0m0.000s
$ time ./fibonacci 27
Fibonacci( 27 ) =      196418

real	0m0.002s
user	0m0.000s
sys	0m0.000s
$ time ./fibonacci 47
Fibonacci( 47 ) =  2971215073

real	0m0.002s
user	0m0.000s
sys	0m0.000s

[Karl L.]

Earlier today I decided to take a short break from the project I was working on, to fix the second problem I identified in your Fibonacci Number calculator. If I were implementing this for an important project, I probably would have used a library (such as the GNU MP Bignum Library) to handle the calculation of extremely large numbers. It was not really an efficient use of my time to reinvent the wheel by implementing complete support for calculating Fibonacci Numbers far larger than the largest unsigned integer type in C, but it was fun. My revision of the program that can calculate arbitrarily large Fibonacci Numbers is below. I verified its implementation against a known list of the first 300 Fibonacci Numbers.

// fibonacci-large.c

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

/* doubly-linked list structure to support arbitrarily large Fibonacci Numbers */
struct FibNum
{
    uint32_t i; // Part of a Fibonacci Number
    struct FibNum * prev; // Previous link in the list
    struct FibNum * next; // Next link in the list
};

/* Fibonacci Number type */
typedef struct FibNum * __fib_num_t;

/*
Instantiate a Fibonacci Number.

Return Value:
    An initialized Fibonacci Number structure will be returned unless enough
    memory cannot be allocated, in which case NULL will be returned.
*/
struct FibNum * new_fib_num()
{
    __fib_num_t p; // Pointer to our new stucture
    
    p = malloc( sizeof( struct FibNum ) );
    if( !p ) return NULL;
    
    p->i = 0;
    p->prev = NULL;
    p->next = NULL;
    
    return p;
}

/*
Free the memory allocated for a Fibonacci Number.

Remarks:
    Although FibNum is a doubly-linked list, this function will only traverse
    the list forwards. Therefore you should always provide the first link in
    the list (where p->prev == NULL) to ensure that the entire list is freed.
    Be diligent; no one wants memory leaks!

Arguments:
    p [in]          Fibonacci Number to be deallocated
*/
void free_fib_num( struct FibNum * p )
{
    __fib_num_t t; // Temporary swap value
    
    while( p )
    {
        t = p;
        p = p->next;
        free( t );
    }
}

/*
Add two Fibonacci Numbers.

Arguments:
    p1 [in]         First number to add
    p2 [in]         Second number to add

Return Value:
    The Fibonacci Number representing the sum of the two input numbers will be
    returned unless an error occurs (probably due to insufficient memory), in
    which case NULL will be returned instead.
*/
struct FibNum * add_fib_num( const struct FibNum * p1, const struct FibNum * p2 )
{
    __fib_num_t pb = new_fib_num(); // Fibonacci Number representing the sum of p1 and p2
    __fib_num_t pr = NULL; // Pointer to the last link in the sum list (pb)
    uint64_t j = 0; // Temporary result of p1 + p2
    uint32_t overflow = 0; // High part of the sum which does not fit in the current 32-bit integer
    
    char buffer[20]; // 64-bit unsigned integer conversion buffer
    int length; // Number of characters in the buffer
    
    if( !pb ) return NULL;
    
    while( p1 || p2 )
    {
        if( pr )
        {
            pr->next = new_fib_num();
            if( !pr->next ) goto add_fib_num_fail;
            pr->next->prev = pr;
            pr = pr->next;
        }
        else
        {
            pr = pb;
        }
        
        j = overflow;
        
        if( p1 )
        {
            j += p1->i;
            p1 = p1->next;
        }
        if( p2 )
        {
            j += p2->i;
            p2 = p2->next;
        }
        
        length = sprintf( buffer, "%llu", j );
        if( length < 1 ) goto add_fib_num_fail;
        if( length > 9 )
        {
            if( sscanf( buffer + (length - 9), "%lu", &(pr->i) ) != 1 ) goto add_fib_num_fail;
            buffer[length - 9] = '\0';
            if( sscanf( buffer, "%lu", &overflow ) != 1 ) goto add_fib_num_fail;
        }
        else
        {
            pr->i = j;
            overflow = 0;
        }
    }
    
    if( overflow )
    {
        pr->next = new_fib_num();
        if( !pr->next ) goto add_fib_num_fail;
        pr->next->prev = pr;
        pr = pr->next;
        pr->i = overflow;
    }
    
    return pb;
    
    add_fib_num_fail:
    free_fib_num( pb );
    return NULL;
}

/*
Convert the given Fibonacci Number to a null-terminated string.

Arguments:
    p [in]          Fibonacci Number to stringify
    buffer [out]    Buffer to hold the string representing the Fibonacci Number
    size [in]       Size of the buffer

Return Value:
    The number of characters that would have been written if the buffer had
    been sufficiently large (not including the null terminating character) will
    be returned. If an encoding error occurs, a negative number will be
    returned instead.
*/
int str_fib_num( const struct FibNum * p, char * buffer, size_t size )
{
    int ret = 0; // Total number of characters written to the buffer
    int length; // snprintf() return value
    
    // Standard specifiers to properly format the output string
    const char * initial_format = "%lu";
    const char * zero_format = "%09lu";
    const char * format = initial_format;
    
    while( p->next ) p = p->next;
    
    while( p )
    {
        length = snprintf( buffer, size, format, p->i );
        if( length < 0 ) return length;
        if( format == initial_format ) format = zero_format;
        
        buffer += length;
        size -= length;
        ret += length;
        p = p->prev;
    }
    
    return ret;
}

/*
Compute the Fibonacci Number for the given index.

Arguments:
    n [in]          Index whose Fibonacci Number you wish to calculate

Return Value:
    The Fibonacci Number associated with the given index will be returned
    unless an error occurs, in which case NULL will be returned instead.
*/
struct FibNum * fibonacci( unsigned int n )
{
    __fib_num_t n1; // fibonacci( n - 1 )
    __fib_num_t n2; // fibonacci( n - 2 )
    __fib_num_t t1; // Temporary swap value #1
    __fib_num_t t2; // Temporary swap value #2
    
    n1 = new_fib_num();
    if( !n1 ) return NULL;
    n1->i = 1;
    
    n2 = new_fib_num();
    if( !n2 )
    {
        free_fib_num( n1 );
        return NULL;
    }
    n2->i = 0;
    
    if( n == 0 || n == 1 )
    {
        free_fib_num( n2 );
        n1->i = n;
        return n1;
    }
    
    for( unsigned int i = 2; i <= n; i++ )
    {
        t1 = n1;
        n1 = add_fib_num( n2, t1 );
        if( !n1 )
        {
            free_fib_num( n2 );
            free_fib_num( t1 );
            return NULL;
        }
        t2 = n2;
        n2 = t1;
        free_fib_num( t2 );
    }
    
    free_fib_num( n2 );
    return n1;
}

/*
Calculate the Fibonacci Number assocated with the number given by the user.
*/
int main( int argc, char * argv[] )
{
    __fib_num_t result; // Resulting Fibonacci Number
    char buffer[4096]; // String representing the result
    unsigned int number; // Number input by the user
    
    // Obtain the number to calculate from the user.
    if( argc > 1 )
    {
        if( argc != 2 )
        {
            fprintf( stderr, "Too many arguments!\n" );
            printf( "Syntax: %s [index]\n", argv[0] );
            return 1;
        }
        
        if( sscanf( argv[1], "%u", &number ) != 1 )
        {
            fprintf( stderr, "Invalid argument: %s\n", argv[1] );
            printf( "Syntax: %s [index]\n", argv[0] );
            return 2;
        }
    }
    else
    {
        printf( "%s", "Enter an integer: " );
        scanf( "%u", &number );
    }
    
    // Calculate the Fibonacci Number associated with the input value.
    result = fibonacci( number );
    if( !result )
    {
        fprintf( stderr, "Fibonacci( %u ) = ?\n", number );
        free_fib_num( result );
        return 3;
    }
    
    // Generate the result string.
    if( str_fib_num( result, buffer, sizeof( buffer )/sizeof( buffer[0] ) ) < 0 )
    {
        fprintf( stderr, "Fibonacci( %u ) = ?\n", number );
        free_fib_num( result );
        return 4;
    }
    
    // Display the result.
    printf( "Fibonacci( %u ) = %s\n", number, buffer );
    free_fib_num( result );
    
    return 0;
}