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?

Started by
Terabojin
, Oct 14 2013 16:16

5 replies to this topic

Posted 14 October 2013 - 23:18

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

Posted 15 October 2013 - 01:24

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.

Posted 15 October 2013 - 05:00

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

Posted 16 October 2013 - 07:20

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; }