Saturday, April 15, 2006

What is the essential difference between Dynamic Programming and Recursion?

Digging out the net I found the answer here. I think it gives the appropriate answer in a pretty terse manner:

The essential difference is that Dynamic Programming keeps its intermediate results whereas recursion does not. This makes a huge difference to performance when a recursive function is called repeatedly with the same arguments. In fact Dynamic Programming is nothing more than recursion with the addition of a caching strategy.

No comments: