It is very simple to implement programs that recursively calculate fib(n), that is the nth fibonacci number, pretty much identically to the mathematical definition of fib(n). But the problem with such programs is that they’re very slow (without DP, anyways.) O(fib(n)) slow to be specific. I realized that there would always be exactly fib(n) calls to the fib function, and this got me thinking of writing a program to calculate fib(n) by having a global counter, and then simply incrementing that counter each time fib is called.

I implemented this in C as such

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdlib.h>
#include <stdio.h>

int fib_real(int n)
{
        if (n <= 2) {
                return 1;
        } else {
                return fib_real(n-1) + fib_real(n-2);
        }
}

int count = 1;
void fib_hack(int n)
{
        if (n <= 2) {
                return;
        } else {
                count++;
                fib_hack(n-1);
                fib_hack(n-2);
        }
}

int main(int argc, char *argv[])
{
        printf("Fib real: %d\n", fib_real(atoi(argv[1])));

        fib_hack(atoi(argv[1]));
        printf("Fib hack: %d\n", count);

        return 0;
}

This program also contains the standard recursive definition of fib(n), and then shows the result of both. Of course the thing to note is that the “real” function as implemented here is just as slow as the hack.