Question

So I have this function that I m trying to convert from a recursive algorithm to an iterative algorithm. I m not even sure if I have the right subproblems but this seems to determined what I need in the correct way, but recursion can t be used you need to use dynamic programming so I need to change it to iterative bottom up or top down dynamic programming.

The basic recursive function looks like this:

Recursion(i,j) {
    if(i > j) {
        return 0;
    }
    else {
        // This finds the maximum value for all possible
        // subproblems and returns that for this problem
        for(int x = i; x < j; x++) {
            if(some subsection i to x plus recursion(x+1,j) is > current max) {
                max = some subsection i to x plus recursion(x+1,j)
            }
        }  
    }
}

This is the general idea, but since recursions typically don t have for loops in them I m not sure exactly how I would convert this to iterative. Does anyone have any ideas?

Answer 1

You have a recursive function that can be summarised as this:

recursive(i, j):
    if stopping condition:
        return value

    loop:
        if test current value involving recursive call passes:
            set value based on recursive call

   return value # this appears to be missing from your example

(I am going to be pretty loose with the pseudo code here, to emphasize the structure of the code rather than the specific implementation)

And you want to flatten it to a purely iterative approach. First it would be good to describe exactly what this involves in the general case, as you seem to be interested in that. Then we can move on to flattening the pseudo code above.

Now flattening a primitive recursive function is quite straightforward. When you are given code that is like:

simple(i):
    if i has reached the limit: # stopping condition
        return value

    # body of method here

    return simple(i + 1) # recursive call

You can quickly see that the recursive calls will continue until i reaches the predefined limit. When this happens the value will be returned. The iterative form of this is:

simple_iterative(start):
    for (i = start; i < limit; i++):
        # body here

    return value

This works because the recursive calls form the following call tree:

simple(1)
  -> simple(2)
    -> simple(3)
      ...
        -> simple(N):
            return value

I would describe that call tree as a piece of string. It has a beginning, a middle, and an end. The different calls occur at different points on the string.

A string of calls like that is very like a for loop - all of the work done by the function is passed to the next invocation and the final result of the recursion is just passed back. The for loop version just takes the values that would be passed into the different calls and runs the body code on them.

Simple so far!

Now your method is more complex in two ways:

There are multiple separate statements that make recursive calls
Those statements themselves are within a for loop

So your call tree is something like:

recursive(i, j):
  for (v in 1, 2, ... N):
    -> first_recursive_call(i + v, j):
      -> ... inner calls ...
    -> potential second recursive call(i + v, j):
      -> ... inner calls ...

As you can see this is not at all like a string. Instead it really is like a tree (or a bush) in that each call results in two more calls. At this point it is actually very hard to turn this back into an entirely iterative function.

This is because of the fundamental relationship between loops and recursion. Any loop can be restated as a recursive call. However not all recursive calls can be transformed into loops.

The class of recursive calls that can be transformed into loops are called primitive recursion. Your function initially appears to have transcended that. If this is the case then you will not be able to transform it into a purely iterative function (short of actually implementing a call stack and similar within your function).

This video explains the difference between primitive recursion and fundamentally recursive types that follow:

https://www.youtube.com/watch?v=i7sm9dzFtEI

I would add that your condition and the value that you assign to max appear to be the same. If this is the case then you can remove one of the recursive calls, allowing your function to become an instance of primitive recursion wrapped in a loop. If you did so then you might be able to flatten it.

Answer 2

well unless there is an issue with the logic not included yet, it should be fine

for & while are ok in recursion

just make sure you return in every case that may occur

友情链接