Recursive Memoized Fibonacci in C++

Question

I was reading an article on Wikipedia about memoization, so I wanted to try and apply it. I am fairly new to this subject, so I thought I'd start small. Does the program use memoization correctly? Is there anything that I can improve?

#include <iostream>
int fibonacci(int num, int* memoize);
int main()
{
 int num;
 std::cout << "i: ";
 std:: cin >> num;
 // i will assume that num > 2, just to keep it short and simple
 int* memoize = new int[num + 1];
 memoize[0] = 0;
 memoize[1] = 1;
 // -1 indicates that the value is not within the array
 for (int i = 2; i <= num; i++)
 memoize[i] = -1;
 std::cout << num << "th fibonacci number: " << fibonacci(num, memoize) << std::endl;
 delete [] memoize;
 return 0;
}
int fibonacci(int num, int* memoize)
{
 // if value has not been calculated yet
 if (memoize[num] == -1)
 {
 // calculate it and store it in the array
 memoize[num] = fibonacci(num - 1, memoize) + fibonacci(num - 2, memoize);
 }
 return memoize[num];
}

I read that the recursive solution to fibonacci is not preferred, but I am still trying to figure out the iterative solution.

Answer 1

Not much to say: your code works as advertised, code is readable, formatting is consistent.

Things that could be better though: don't use raw arrays with new unless you absolutely have to. Prefer std::vector, it has a nice interface and manages its own memory. It also has a constructor that lets you fill it with a given value.

std::vector<int> cache(num+1, -1);
cache[0] = 0;
cache[1] = 1;

Then pass that as a std::vector<int>& to your Fibonacci function. No more open-coded loop, no more new[]/delete[], so less chances of bugs and leaks.

Another technique that would avoid that vector at all would be to have the Fibonacci function do its own memoizing, without external state. That's easier on the user, and you can do a more general technique with a static std::map in the function being memoized to keep the state. (This is not thread-safe as is, but a shared vector or raw array isn't either.)

Here's an example:

#include <iostream>
#include <map>
int fibonacci(int num)
{
 static std::map<int, int> cache{{0, 0}, {1, 1}};
 auto found = cache.find(num);
 if (found != std::end(cache)) {
 // For debugging purposes, to check that the cache is doing something
 std::cout << "Found in cache: " << num << " -> " << found->second << '\n';
 return found->second;
 }
 int result = fibonacci(num - 1) + fibonacci(num - 2);
 cache[num] = result;
 return result;
}

And the corresponding main: I've moved the call to fibonacci out of the printout statement, don't hide important function calls in there.

int main()
{
 int num;
 std::cout << "i: ";
 // TODO: input validation
 std::cin >> num;
 int res = fibonacci(num);
 std::cout << num << "th fibonacci number: " << res << std::endl;
}

Of course this is a bit overkill for the situation at hand. There are more general techniques, you'll find some for example here: Writing Universal memoization function in C++11.

---

The iterative approach is much more efficient and pretty simple. In pseudo code:

fib(n):
 prev = 0
 curr = 1
 i = 2
 while i <= n
 next = prev + curr
 prev = curr
 curr = next
 i++
 return curr

• DominikS: Very interesting answer! One thing remains unclear to me: If you would run this code only once, with a huge value of num, the cache gets built up on the go. Now, does your code still reduce the stack memory usage? My guess would be that fib gets called O(n) instead O(2^n) times - is this correct?