08/30/2002 Entry: "I Hate Recursion"
Posted by Maynard @ 01:54 PM MST

I Hate Recursion

It's difficult, it's frequently implemented poorly, it tends to run slowly, and beginning freshmen rarely get it right for their homework assignments. That's why I'm writing this little snippet of code. One frequent assignment freshmen get is to write a recursive program that calculates the nth Fibonacci number. That's the sequence that goes 1, 1, 2, 3, 5, 8, etc., where the nth term is the sum of the n-1 and n-2 terms. Read on to see the solution to this recursively and non-recursively, and learn why the non-recursive way is better. FYI, the programming icon shows an elephant stuck in the La Brea Tar Pits. Look up Fred Brooks on Amazon.com if you don't get it.

Recursive Solution

#include <stdio.h>

long Fibonacci(long n)
{
    if ( n == 0 || n == 1 )
        return n; //base case
    else if ( n > 0 )
        return Fibonacci(n-1) + Fibonacci(n-2); //recursive case
    else
        return -1; //error case
}

int main(void)
{
    long x = Fibonacci(10);
    printf("%d\n", x);
    return 0;
}

You'll note that this solution calls Fibonacci a variable number of times, depending on what n is. Specifically, for each call to Fibonacci, 2 more calls are made. That leads to exponential growth as n gets larger. Very bad. Yet this is often the first recursive algorithm taught to freshmen when they take an introductory programming class.

Dynamic Programming Solution

#include <stdio.h>

int main(void)
{
    int Fibonacci[10]; // create an array of 10 ints, or longs, or whatever
    Fibonacci[0] = 1; // set the first 2 values
    Fibonacci[1] = 1;
    for(int n=2; n<10; n++) // for all the rest of the values
        Fibonacci[n] = Fibonacci[n-1] + Fibonacci[n-2]; // set the nth value to the sum of the 2 previous values
    printf("%d\n", Fibonacci[9]); // print out the last value
    return 0;
}

The Dynamic Solution is dynamic because the amount of space needed for the solution is always different. However, the algorithm grows linearly as n grows. That means that the dynamic solution will run faster. Fast is good in programming.