java - 如何将外部递归程序转换为非递归形式(使用堆栈而不是CPS)？

Question

关于如何将递归转换为非递归的问题很多，我也可以将一些递归程序转换为非递归形式注意:我用的是通用的方式(user defined Stack)，因为我觉得很容易理解，而且我用的是Java，所以不能用GOTO关键字。

事情并不总是那么顺利，当我遇到回溯时，我就卡住了。例如，子集问题。我的代码在这里:recursive call with loop

当我使用用户定义的 Stack 将其转换为非递归形式时。我不知道如何处理循环(在循环中存在递归调用)。

google了一下发现有很多方法比如CPS。我知道有一个子集问题的迭代模板。但我只想使用用户定义的堆栈来解决。

有人可以提供一些线索将这种递归(带循环的递归)转换为非递归形式(通过使用用户定义的 Stack，而不是 CPS 等)吗？

这是我的代码 recursive to non-recusive (Inorder-Traversal)，因为递归调用没有循环，所以我很容易做到。同样，当具有返回值的递归程序时，我可以使用引用并将其作为参数传递给函数。从代码中，我使用Stack来模拟递归调用，并使用“状态”变量到下一个调用点(因为java不允许使用GOTO)。

以下是我收集的资料。好像都不能满足我提的问题(有的用java不允许的goto，有的很简单recursive就是没有嵌套的递归调用或者带loop的递归调用)。

1 Old Dominion University

2 codeproject

--------------------------------分割线------------ ----------------------------

谢谢大家。在我发布问题之后......我花了整整一夜才弄明白。这是我的解决方案:non-recursive subset problem solution ，代码的注释是我的想法。

总结一下。我之前卡住的是如何处理foo-loop，实际上，我们可以忽略它。因为我们使用的是loop+stack，所以可以简单判断是否满足条件。

Answer 1

在您的堆栈上，您是否考虑过压入 i(迭代变量)？通过这样做，当您弹出该值时，您知道在压入堆栈之前您处于循环的哪次迭代，因此，您可以迭代到下一个 i 并继续您的算法。