将递归函数转换为非递归函数(Converting A Recursive Function into a Non

将递归函数转换为非递归函数(Converting A Recursive Function into a Non-Recursive Function)

我正在尝试将递归函数转换为伪代码中的非递归解决方案。 我遇到问题的原因是该方法有两个递归调用。 任何帮助都会很棒。 谢谢。

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); } }

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); } }

最满意答案

将递归过程转换为迭代过程的texbook方法只是用堆栈替换递归调用并运行“do循环”直到堆栈为空。

请尝试以下方法：

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; } }

原来的函数有两个recusive调用，为什么只有一个堆栈呢？ 忽略第二次递归调用的要求，你可以很容易地看到第一个递归调用（ mystery(a, mid); ）可以实现为一个简单的循环，其中b假设每次迭代的mid值 - 没有其他需要被“记住” ”。 因此将其转换为循环并简单地将重复所需的参数推送到堆栈，添加外部循环以运行堆栈。 完成。

通过一些创造性思维，任何递归函数都可以使用堆栈转换为迭代函数。

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.