Should I use recursion or memoization for an algorithm?

Question

If I have a choice to use recursion or memoization to solve a problem which should I use? In other words if they are both viable solutions in that they give the correct output and can be reasonably expressed in the code I'm using, when would I use one over the other?

Answer 1

Recursion has a performance penalty associated with the creation of stack frames, memoization's penalty is the caching of the results, If performance is a concern only way to know for sure will be to test in your application.

In my personal opinion I'd go with the method which is the easiest to use and understand first, which in my opinion is recursion. Until you demonstrate a need for memoization.

Answer 2

Not sure I can say without knowing the problem. Often you'd want to use memoization with recursion. Still, memoization is likely to be significantly quicker than recursion if you can in fact use it as an alternative solution. They both have performance issues, but they vary differently with the nature of the problem/size of input.

Answer 3

I pick memoization because it's usually possible to access more heap memory than stack memory.

That is, if your algorithm is run on a lot of data, in most languages you'll run out of stack space recursing before you run out of space on the heap saving data.

Answer 4

It depends on what you're going for. dynamic programming (memoization) is almost always faster. Often by a LOT. (ie, cubic to squared, or exponential to poly), but in my experience, recursion is easier to read and debug.

Then again, a lot of people avoid recursion like the plague, so they don't find it easy to read...

Also, (third hand?) I find that it's easiest to find the Dynamic solution after I've come up with the recursive one, so I end up doing both. But if you've already got both solutions, Dynamic may be your best bet.

I'm not sure if I've been helpful, but there you go. As in many things of algorithm choice, YMMV.

Answer 5

They are not mutually exclusive. You can use them both.

Personally, I'd build the base recursive function first, and add memoization afterwards, as an optimisation step.

Answer 6

If your problem is a recursive one, what choice do you have but to recurse?

You can write your recursive function in a way that short circuits using memoization, to gain maximum speed for the second call.

Answer 7

Recursion does not need to use a significant amount stack space if the problem can be solved using tail recursion techniques. As said previously, depends on the problem.

Answer 8

The rule of thumb to use is based on the amount of overlap the subproblems have. If you're calculating fibonacci numbers (the classic recursion example) there's a lot of needless recalculation done if you use recursion.

For example, to calculate F(4), I need to know F(3) and F(2), so I calculate F(3) by calculating F(2) and F(1), and so on. If I used recursion, I just calculated F(2) and most other F(n) twice. If I use memoization, I can just look the value up.

If you're doing binary search there is no overlap between subproblems, so recursion is okay. Splitting the input array in half at each step results in two unique arrays, which represent two subproblems with no overlap. Memoization wouldn't be a benefit in cases like this.

Answer 9

In the usual case, you are faced with two criteria which help with your decision:

• Run time
• Readability

Recursive code is usually slower but much more readable (not always, but most often. As it was said, tail recursion can help if your language supports it - if not, there is not much you can do).

The iterative version of a recursive problem is usually faster in terms of runtime but the code is hard to understand and, because of that, frail.

If both versions have the same run time and the same readability, there is no reason to choose either over the other. In this case, you have to check other things: Will this code change? How about maintenance? Are you comfortable with recursive algorithms or are they giving you nightmares?

Answer 10

Memoization is just a caching method that happen to be commonly used to optimize recursion. It cannot replace recursion.

Answer 11

var memoizer = function (fund, memo) {
    var shell = function (arg) {
        if (typeof memo[arg] !== 'number') {
            memo[arg] = fund(shell, arg);
        }
        return memo[arg];
    };
    return shell;
};

var fibonacci = memoizer(function (recur, n) { return recur(n - 1) + recur(n - 2); }, [0, 1]);

use both!

Answer 12

I believe you might be confusing memoization (which is, as others have noted, an optimization strategy for recursive algorithms) with dynamic programming (which simulates a recursive solution but does not actually use recursion). If that was your question I'd say it would depend on your priorities: high runtime efficiency (dynamic programming) or high readability (memoization, as the recursive solution of the problem is still present in the code).

Answer 13

I don't agree with Tomalak's assertion that with a recursive problem you have no choice but to recurse?

The best example is the above-mentioned Fibonacci series. On my computer the recursive version of F(45) (F for Fibonacci) takes 15 seconds for 2269806339 additions, the iterative version takes 43 additions and executes in a few microseconds.

Another well-known example is Towers of Hanoi. After your class on the topic it may seem like recursion is the only way to solve it. But even here there's a iterative solution, although it's not as obvious as the recursive one. Even so, the iterative is the faster, mainly because no expensive stack-operations are required.

In case you're interested in the non-recursive version of Towers of Hamoi, here's the Delphi source code:

procedure TForm1.TowersOfHanoi(Ndisks: Word);
var
  I: LongWord;
begin
  for I := 1 to (1 shl Ndisks) do
    Memo1.Lines.Add(Format('%4d: move from pole %d to pole %d',
      [I, (I and (I - 1)) mod 3, (I or (I - 1) + 1) mod 3]));
  Memo1.Lines.Add('done')
end;