What's the difference between recursion, memoization & dynamic programming? [duplicate]

Question

Possible Duplicate:
Dynamic programming and memoization: top-down vs bottom-up approaches

I have gone through a lot of articles on this but can't seem to make sense of it. At times recursion and dynamic programming looks the same and at others memoization & dynamic programming look alike. Can someone explain to me what's the difference?

P.S. It will also be helpful if you could point me to some code using the three approaches on the same problem. (e.g. the Fibonacci series problem, I think every article I read used recursion but referred to it as dynamic programming)

Answer 1

Consider calculating the fibonacci sequence:

Pure recursion:

int fib(int x) {     if (x < 2)         return 1;      return fib(x-1) + fib(x-2); } 

results in exponential number of calls.

Recursion with memoization/DP:

int fib(int x) {     static vector<int> cache(N, -1);      int& result = cache[x];      if (result == -1)     {         if (x < 2)             result = 1;         else             result = fib(x-1) + fib(x-2);     }      return result; } 

Now we have linear number of calls the first time, and constant thereafter.

The above method is called "lazy". We calculate the earlier terms the first time they are asked for.

The following would also be considered DP, but without recursion:

int fibresult[N];  void setup_fib() {     fibresult[0] = 1;     fibresult[1] = 1;     for (int i = 2; i < N; i++)        fibresult[i] = fibresult[i-1] + fibresult[i-2]; }  int fib(int x) { return fibresult[x]; } 

This way may be described as "eager", "precaching" or "iterative". Its faster overall but we have to manually figure out the order the subproblems need to be calculated in. This is easy for fibonacci, but for more complex DP problems it gets harder, and so we fall back to the lazy recursive method if it is fast enough.

Also the following is neither recursion nor DP:

int fib(int x) {     int a = 1;     int b = 1;     for (int i = 2; i < x; i++)     {         a = a + b;         swap(a,b);     }     return b; } 

It uses constant space and linear time.

Also I will mention for the sake of completeness there is a closed form for fibonacci that uses nether recursion nor DP that allows us to calculate in constant time the fibonacci term using a mathematic formula based on the golden ratio:

http://www.dreamincode.net/forums/topic/115550-fibonacci-closed-form/