我正在尝试将递归函数转换为伪代码中的非递归解决方案。我遇到问题的原因是该方法中有两个递归调用。
任何帮助都会很棒。谢谢。
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);
}
}
将递归过程转换为迭代过程的texbook方法只是将递归调用替换为堆栈并运行“执行循环”,直到堆栈为空。
尝试以下操作:
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;
}
}
原始函数有两个调用调用,所以为什么只有一个堆栈?忽略以下要求第二次递归调用,您可以轻松看到第一个递归调用(mystery(a, mid);
)可以实现为一个简单的循环,其中b
假定值为mid
在每次迭代中-无需“记住”其他任何内容。所以把它变成一个循环然后简单地推动撤回堆栈所需的参数,添加一个外部循环来运行堆栈。完成。
[经过一些创造性的思考,可以使用堆栈将任何递归函数转换为迭代函数。
这似乎更有趣,它将导致以递归函数特定的顺序显示从a到(b-1)的所有数字。请注意,所有“左”中点都在任何“右”中点之前打印。
void mystery (int a, int b) {
if (b > a) {
int mid = roundDown(a+b)/2;
print mid;
mystery(a, mid);
mystery(mid+1, b);
}
}
例如,如果a = 0,b = 16,则输出为:8 4 2 1 0 3 6 5 7 12 10 9 11 14 13 15
这是正在发生的事情。您有一根长杆,正在将其分成两部分。然后将这两个部分分成两部分。您可以对每个子部分执行此操作,直到该部分的长度变为1。
您将如何做?
假设您必须在中点折断杆。我们将把标记放在垃圾箱中以便进一步削减。注意:每个零件都会生成两个新零件,因此我们需要2 n框来存储子零件。
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:我没有尝试过此代码。这只是一个伪代码。在我看来,它应该完成这项工作。让我知道是否可以尝试。它将验证我的算法。它基本上是数组中的b树。
此示例以递归方式拆分数字范围,直到该范围减小为单个值。输出显示数字的结构。单个值按顺序输出,但根据左侧的第一个拆分函数分组。
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);
}