0

I have to convert this recursive algorithm into an iterative one:

  int alg(int A[], int x, int y, int k){
    int val = 0;

    if (x <= y){
      int z = (x+y)/2;

      if(A[z] == k){
        val = 1;
      }

      int a = alg(A,x,z-1,k);

      int b;

      if(a > val){
        b = alg(A,z+1,y,k);
      }else{
        b = a + val;
      }

      val += a + b;
  }

  return val;
 }

I tried with a while loop, but I can't figure out how I can calculate "a" and "b" variables, so I did this:

  int algIterative(int A[], int x, int y, int k){
   int val = 0;

   while(x <= y){
     int z = (x+y)/2;

     if(A[z] == k){
        val = 1;
     }

     y = z-1;
   }
  }

But actually I couldn't figure out what this algorithm does. My questions are:

What does this algorithm do? How can I convert it to iterative? Do I need to use stacks?

Any help will be appreciated.

Improve this question
7
  • "I need to use stacks?" Basically yes. That's what a recursive call does more or less with all in / out parameters. Commented Feb 25, 2019 at 9:47
  • 1
    "What does this algorithm do?" You should give us some more context. Is this part of some larger project? Commented Feb 25, 2019 at 9:52
  • Do I need to use stacks? Not necessarily. You can calculate factorials recursively, but iterative variant does not need a stack. It depends on the concrete problem. Commented Feb 25, 2019 at 10:08
  • Thank you for your responses. As I understood I can do this with stacks or not, right? To @Jabberwocky this is a university exercise so there is no larger context behind, I think is a random algorithm Commented Feb 25, 2019 at 10:18
  • @Andrew21111 you should mention this in the question. Commented Feb 25, 2019 at 10:20

2 Answers 2

Reset to default
2

I am not sure that alg computes anything useful.

It processes the part of the array A between the indexes x and y, and computes a kind of counter.

If the interval is empty, the returned value (val) is 0. Otherwise, if the middle element of this subarray equals k, val is set to 1. Then the values for the left and right subarrays are added and the total is returned. So in a way, it counts the number of k's in the array.

But, if the count on the left side is found to be not larger than val, i.e. 0 if val = 0 or 0 or 1 if val = 1, the value on the right is evaluated as the value on the left + val.

Derecursivation might be possible without a stack. If you look at the sequence of subintervals that are traversed, you can reconstruct it from the binary representation of N. Then the result of the function is the accumulation of partials results collected along a postorder process.

If the postorder can be turned to inorder, this will reduce to a single linear pass over A. This is a little technical.

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

6 Comments

Yes, but I can't figure out why, Is this algorithm useless? There's a simple way to make it iterative?
Right is only added if left has been found..., i. e. {n, m, k, k} should still result in 0, shoudn't it?
@Aconcagua: don't know what you mean.
In the case of x == y, a will be 0 (next recursion is empty array), thus b will be val + 0 == val; Thus final result will be val + val, i. e. either 0 or 2. Using this as a base, you'll discover that all results necessarily are even; especially: a == 1 can never be the case. a > 0 applies only if there is a k found in right half at the right places (not the case in the left half {n}), thus the right half ({k, k}) is not recursed into at all. So in above example, result will be 0 (as m != k as well).
@Aconcagua: this confirms that it is a fake program.
|
1

A simple way could be smt like this with the aid of a two dimensional array:

int n = A.length;
int[][]dp = new int[n][n];
for(int i = n - 1;i >= 0; i--){
    for(int j = i; j < n; j++){
        // This part is almost similar to the recursive part.
        int z = (i+j)/2;
        int val = 0;
        if(A[z] == k){
          val = 1;
        }

        int a = z > i ?  dp[i][z - 1] : 0;

        int b;

        if(a > val){
           b = (z + 1 <= j) ? dp[z + 1][j] : 0;
        }else{
           b = a + val;
        }

        val += a + b;
        dp[i][j] = val; 
    }
}
return dp[0][n - 1];

Explanation:

Notice that for i, it is decreasing, and j, it is increasing, so, when calculate dp[x][y], you need dp[x][z - 1] (with z - 1 < j) and dp[z + 1][j] (with z >= i), and those values should already be populated.

Improve this answer

9 Comments

It seems a good solutions, I will try and let you know! Thank you so much!
Using an NxN array is total overkill. It will take N² elements, while a stack implementation only requires Log N elements.
@YvesDaoust you're totally right, but I never used stacks and I don't know how to do it.
However, I tried this algorithm, but it not always gives the same result as the recursive one
@YvesDaoust yup, however, this should be easier to grasp than the stack implementation :), so pros and cons.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.