Memoization Rocks

// Testing.cpp : Defines the entry point for the console application.
//

#include "iostream"

using namespace std;

int results[50];


long memoized_fibonacci_recurs(int results[],int n) {

long val = 0;
if (results[n] != -1)
return results[n];

if (n == 1)

val = 1;

else if (n == 2)

val = 1;

else {

val = memoized_fibonacci_recurs(results,n - 2);
val = val + memoized_fibonacci_recurs(results,n - 1);
}

results[n] = val;

return val;

}

long fib(int num)
{
if ( num == 0 )
return 0;
if ( num == 1)
return 1;
else
return (fib(num-1) + fib(num-2));
}


long memoized_fibonacci(int n) {

for(int i = 0; i < 50; i++)

results[i] = -1; // -1 means undefined

return memoized_fibonacci_recurs(results,n);

}




int main(int argc, char*argv[])
{
long num = fib(40);

long num1 = memoized_fibonacci(40);

cout << "Computed Value is:" << num << endl;
cout << "Memoized Computed Value is:" << num1 << endl;
}