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);
}
}
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
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.
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.
O(log(b-a)) extra space, while the proposed algorithm requires O(2^(b-a)).O(2^(b-a)) space. The idea is to do DFS, so the only thing we store is the path from the root of the tree to the nodes, hence O(log(b-a)).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);
}