#include <iostream>
#include <string>
#include <cstdlib>
#include "fib.h"
using namespace std;

//This technique is called MEMOIZATION
//Storing results in a table so that you never have to compute them again!

int *fs;

int main (int argc, char **argv) {

 memoinit ();
 for (int i=59; i >= 0; i-=2)
  cout << "fib (" << i << ") = " << fib(i) << endl;

// loopfib ();
 memocleanup;
 return 0;
}

int fib (int n) {

 if (fs[n]!=-1) return fs[n]; //If I already computed this one, just return it.
 int a = fib(n-2);
 int b = fib(n-1);
 fs[n] = a+b;  //New answer, just store it!
 return fs[n];
}

void loopfib () {

 int *f = new int[60];
 f[0] = 0;
 f[1] = 1;
 for (int i=2; i < 60; i++)
  f[i] = f[i-2]+f[i-1];
 for (int i=0; i < 60; i++)
  cout << "fib(" << i << ") = " << f[i] << endl;
 delete[] f;
}

void memoinit () {

 fs = new int[60];
 fs[0] = 0;
 fs[1] = 1;
 for (int i=2; i < 60; i++)
  fs[i] = -1;
}

void memocleanup () {

 delete[] fs;
}