Recursive Memoized Fibonacci in C++
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&lt;int&gt; cache(num+1, -1);
cache[0] = 0;
cache[1] = 1;


Then pass that as a std::vector&lt;int&gt;&amp; 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 &lt;iostream&gt;
#include &lt;map&gt;

int fibonacci(int num)
{
  static std::map&lt;int, int&gt; 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 &lt;&lt; "Found in cache: " &lt;&lt; num &lt;&lt; " -&gt; " &lt;&lt; found-&gt;second &lt;&lt; '\n';
    return found-&gt;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 &lt;&lt; "i: ";
  // TODO: input validation
  std::cin &gt;&gt; num;

  int res = fibonacci(num);
  std::cout &lt;&lt; num &lt;&lt; "th fibonacci number: " &lt;&lt; res &lt;&lt; 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 &lt;= n
    next = prev + curr
    prev = curr
    curr = next
    i++
  return curr