Should I use recursion or memoization for an algor

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

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 2

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 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

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 5

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;

Answer 6

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