CODEWITHSUNDEEP
algorithmrecursion
Ashton
Ashton

Reputation: 131

Converting A Recursive Function into a Non-Recursive Function

I'm trying to convert a recursive function into a non-recursive solution in pseudocode. The reason why I'm running into problems is that the method has two recursive calls in it.

Any help would be great. Thanks.

void mystery(int a, int b) {
    if (b - a > 1) {
        int mid = roundDown(a + b) / 2; 
         print mid; 
         mystery(a, mid); 
         mystery(mid + 1, b); 
     }
}

Upvotes: 0

Views: 1235

Answers (4)

rcgldr
rcgldr

Reputation: 28828

This one seems more interesting, it will result in displaying all numbers from a to (b-1) in an order specific to the recursive function. Note that all of the "left" midpoints get printed before any "right" midpoints.

void mystery (int a, int b) { 
    if (b > a) { 
         int mid = roundDown(a + b) / 2; 
         print mid; 
         mystery(a, mid); 
         mystery(mid + 1, b); 
    } 
}

For example, if a = 0, and b = 16, then the output is:

8 4 2 1 0 3 6 5 7 12 10 9 11 14 13 15

Upvotes: 1

rcgldr
rcgldr

Reputation: 28828

This example recursively splits a range of numbers until the range is reduced to a single value. The output shows the structure of the numbers. The single values are output in order, but grouped based on the left side first split function.

void split(int a, int b)
{
    int m;
    if ((b - a) < 2) {      /* if size == 1, return */
        printf(" | %2d", a);
        return;
    }
    m = (a + b) / 2;        /* else split array */
    printf("\n%2d %2d %2d", a, m, b);
    split(a, m);
    split(m, b);
}

Upvotes: 0

NealB
NealB

Reputation: 16928

The texbook method to turn a recursive procedure into an iterative one is simply to replace the recursive call with a stack and run a "do loop" until the stack is empty.

Try the following:

push(0, 16);     /* Prime the stack */
call mystery;
...

void mystery {
do until stackempty() {   /* iterate until stack is empty */
  pop(a, b)               /* pop and process... */
  do while (b - a >= 1) { /* run the "current" values down... */
    int mid = roundDown(a+b)/2;
    print mid;  
    push(mid+1, b);       /* push in place of recursive call */
    b = mid;
  }
}

The original function had two recusive calls, so why only a single stack? Ignore the requirements for the second recursive call and you can easily see the first recursive call (mystery(a, mid);) could implemented as a simple loop where b assumes the value of mid on each iteration - nothing else needs to be "remembered". So turn it into a loop and simply push the parameters needed for the recusion onto a stack, add an outer loop to run the stack down. Done.

With a bit of creative thinking, any recursive function can be turned into an iterative one using stacks.

Upvotes: 0

Nishant
Nishant

Reputation: 55866

This is what is happening. You have a long rod, you are dividing it into two. Then you take these two parts and divide it into two. You do this with each sub-part until the length of that part becomes 1.

How would you do that?

Assume you have to break the rod at mid point. We will put the marks to cut in bins for further cuts. Note: each part spawns two new parts so we need 2n boxes to store sub-parts.

len = pow (2, b-a+1)      // +1 might not be needed
ar = int[len]             // large array will memoize my marks to cut
ar[0] = a                 // first mark
ar[1] = b                 // last mark 
start_ptr = 0             // will start from this point
end_ptr = 1               // will end to this point
new_end = end_ptr         // our end point will move for cuts

while true:                          //loop endlessly, I do not know, may there is a limit
  while start_ptr < end_ptr:         // look into bins
    i = ar[start_ptr]                //
    j = ar[start_ptr+1]              // pair-wise ends

    if j - i > 1                     // if lengthier than unit length, then add new marks
      mid = floor ( (i+j) / 2 )      // this is my mid
      print mid
      ar[++new_end] = i              // first mark   --|
      ar[++new_end] = mid - 1        // mid - 1 mark --+-- these two create one pair
      ar[++new_end] = mid + 1        // 2nd half 1st mark --|
      ar[++new_end] = j              // end mark          --+-- these two create 2nd pair 

    start_ptr = start_ptr + 2        // jump to next two ends

  if end_ptr == new_end             // if we passed to all the pairs and no new pair
    break                           // was created, we are done.
  else
    end_ptr = new_end               //else, start from sub prolem

PS: I haven't tried this code. This is just a pseudo code. It seems to me that it should do the job. Let me know if you try it out. It will validate my algorithm. It is basically a b-tree in an array.

Upvotes: 0

Related Questions