Can dynamic programming be used with recursion?

Question

I understand why DP is more efficient over than simple recursion.

However, I understood that DP is recursion using memoization technique.

For Fibonacci, like this :

int DP[10000]; //initalized by 0

int f(int num){
    if (DP[num] != 0)
        return DP[num];

    DP[num] = f(num -1) + f(num - 2);
    return DP[num];
}

I always use DP in this way of recursion, and it works quite well on algorithm problems like ACM.

Recently, I knew that most people do not use DP in this way.

They use DP like this :

int fib(int n)
{
  /* Declare an array to store Fibonacci numbers. */
  int f[n+1];
  int i;

  /* 0th and 1st number of the series are 0 and 1*/
  f[0] = 0;
  f[1] = 1;

  for (i = 2; i <= n; i++)
  {
      /* Add the previous 2 numbers in the series
         and store it */
      f[i] = f[i-1] + f[i-2];
  }

  return f[n];
}

this source is from http://www.geeksforgeeks.org/program-for-nth-fibonacci-number/

I don't know this two way's difference.

Are they have same time complexity?

Also, I wonder can my way(recursion + memoization) is called DP?

And is there any disadvantages using my way of DP on algorithm problems?

Note that your first example isn't quite right, because you forgot to actually memoize! — ruakh
– ruakh, Commented Jan 29, 2017 at 5:30

ruakh · Accepted Answer · 2017-01-29 05:23:11Z

5

Also, I wonder can my way(recursion + memoization) is called DP?

I think it's a borderline case. Cormen et al.'s Introduction to Algorithms, Second Edition describes your approach (on page 347) as a "variation of dynamic programming", contrasting it with the "ordinary dynamic programming" of the preceding sections, and referring to it as "memoization" or "memoized recursion".

And is there any disadvantages using my way of DP on algorithm problems?

In your specific example, I think the biggest disadvantage is that you require O(n) stack space, which may be a problem in many environments (stack space is often much more limited than heap space). And although the ordinary-DP version that you quote still uses O(n) space, I think it's much more obvious how to go from there to a version that uses only O(1) space. (And that's true of many other DP problems as well; for example, the greatest-common-subsequence problem requires only O(m + n) space, but a memoized recursive solution requires O(mn) space.)

On the other hand, your approach may be better in some cases where it's not so obvious exactly which subproblems will actually end up being needed. In that case, the memoized recursion approach avoids solving unnecessary cases.

answered Jan 29, 2017 at 5:23

ruakh

185k29 gold badges292 silver badges324 bronze badges

Sign up to request clarification or add additional context in comments.

14 Comments

cuongptnk Over a year ago

Nice. The comparision of stack and heap is cool and also the reducing space. Can you give an example for the last paragraph ? I am still not clear how such a situation is. thx

MBo Over a year ago

Addition: there are terms top-down DP for memoization and bottom-up DP for the second approach

BlakStar Over a year ago

So both momoized recursion and ordinary-DP have same time complexity?(In this case O(n), I guess)

ruakh Over a year ago

@cuongptnk: Not exactly. The repeated values were just so there would be multiple "branches" of deep recursion (i.e., so that for any given first, s[first] == t[last] could be true for multiple values of last); but I'm not suggesting that you should memoize based on the actual contents of s_Left and t_Left and so on. Rather, you should memoize based on L and the indices into s and t. (You can store this in a three-dimensional array.)

ruakh Over a year ago

@cuongptnk: (Having thought about it further, a better way to ensure deep recursion is to say that we want a count of all possible distinct trees with preorder traversal = s and postorder traversal = t. The worst-case number of recursions would then be in a sequence like A-A-A-A-A-A-A-A, where naive recursion takes exponential time but dynamic programming or memoized recursion takes polynomial time.)

|

Collectives™ on Stack Overflow

Can dynamic programming be used with recursion?

1 Answer 1

14 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

14 Comments

Related