Fibonacci numbers in C

The recurrence formula for the \(n\)th Fibonacci number is:

\(
F_{n} = \begin{cases} F_{n – 1} + F_{n – 2} & \textrm{if}\;n > 1\\ 1 &\textrm{if}\;n = 1\\ 0 &\textrm{if}\;n = 0.\end{cases}
\)

A naive recursive implementation of this would be:

unsigned int fib(unsigned int n)
{
	if (n == 0) return 0;
	if (n == 1) return 1;
	return fib(n - 1) + fib(n - 2);
}

But this runs in exponential time because it keeps recalculating the same results in the recursion.

If we add some instrumentation, we can see what it’s doing:

struct calltree {
    unsigned int value;
    struct calltree *left;
    struct calltree *right;
};
typedef struct calltree calltree;

typedef void (*calltreefn)(unsigned int, unsigned int, void *);

calltree *calltree_create(unsigned int value)
{
    calltree *tree = malloc(sizeof(calltree));
    if (tree) {
        tree->value = value;
        tree->left = NULL;
        tree->right = NULL;
    }
    return tree;
}

void calltree_delete(calltree *tree)
{
    if (tree != NULL) {
        calltree_delete(tree->left);
        calltree_delete(tree->right);
        free(tree);
    }
}

void calltree_for_each(const calltree *tree, unsigned int level, calltreefn fun, void *data)
{
    if (tree != NULL) {
        fun(level, tree->value, data);
        calltree_for_each(tree->left, level + 1, fun, data);
        calltree_for_each(tree->right, level + 1, fun, data);
    }
}

unsigned int fib(unsigned int n, calltree **tree)
{
    *tree = calltree_create(n);
	if (n == 0) return 0;
	if (n == 1) return 1;
	return fib(n - 1, &((*tree)->left)) + fib(n - 2, &((*tree)->right));
}

Here is an example program to calculate \(F_{7}\):

void print_call_text(unsigned int level, unsigned int value, void *data)
{
    unsigned int i;
    for (i = 0; i < level; i++) {
        putchar(' ');
    }
    printf("fib(%d)\n", value);
}

int main(void)
{
    calltree *tree;
    fib(7, &tree);
    calltree_for_each(tree, 0, print_call_text, NULL);
    calltree_delete(tree);
    printf("%u\n", result);
	return 0;
}

The call tree produced:

fib(7)
 fib(6)
  fib(5)
   fib(4)
    fib(3)
     fib(2)
      fib(1)
      fib(0)
     fib(1)
    fib(2)
     fib(1)
     fib(0)
   fib(3)
    fib(2)
     fib(1)
     fib(0)
    fib(1)
  fib(4)
   fib(3)
    fib(2)
     fib(1)
     fib(0)
    fib(1)
   fib(2)
    fib(1)
    fib(0)
 fib(5)
  fib(4)
   fib(3)
    fib(2)
     fib(1)
     fib(0)
    fib(1)
   fib(2)
    fib(1)
    fib(0)
  fib(3)
   fib(2)
    fib(1)
    fib(0)
   fib(1)

We can get rid of all of these recursive calls by caching the results instead:

unsigned int fib(unsigned int n)
{
    unsigned int *numbers;
    unsigned int i;
    unsigned int result;
    if (n == 0) return 0;
    numbers = malloc((n + 1) * sizeof(int));
    if (numbers == NULL) {
        return 0;
    }
    numbers[0] = 0;
    numbers[1] = 1;
    for (i = 2; i <= n; i++) {
        numbers[i] = numbers[i - 2] + numbers[i - 1];
    }
    result = numbers[n];
    free(numbers); 
    return result;
}

If we were going to calculate a lot of Fibonacci numbers we could store the cache between calls rather than creating it anew each time.