#include <stdio.h>

/* call_count used to count recursive calls */
long call_count;

unsigned long fib(unsigned int n);
unsigned long fib2(unsigned int n, unsigned long p0, unsigned long p1);

long dumb_fib(long n);

int main()
{
    printf("%12s %12s %12s %12s\n", "N", "Fib(N)", "Dumb", "Smart");
    printf("%12s %12s %12s %12s\n", "-------", "-------", "-------", "-------");
    for (int i = 0; i < 35; ++i) {
        long dumb_result, dumb_count, smart_result, smart_count;
        call_count = 0;
        dumb_result = dumb_fib(i);
        dumb_count = call_count;
        call_count = 0;
        smart_result = fib(i);
        smart_count = call_count;
        if (dumb_result != smart_result)
        {
            printf("OOOPS! Dumb says %d, Smart says %d\n",
                   dumb_result, smart_result);
            break;
        }
        printf("%12d %12d %12d %12d\n", i, dumb_result, dumb_count, smart_count);
    }
    
    return 0;
}

long dumb_fib(long n)
{
    ++call_count;
    
    if (n == 0 || n == 1)
    {
        return n;
    }
    else
    {
        return dumb_fib(n - 2) + dumb_fib(n - 1);
    }
}

unsigned long fib(unsigned int n)
{
    return n == 0 ? 0 : fib2(n, 0, 1);
}


unsigned long fib2(unsigned int n, unsigned long p0, unsigned long p1)
{
  ++call_count;
  return n == 1 ? p1 : fib2(n - 1, p1, p0 + p1);
}