10

我正在从 main() 调用一个函数 fooA，该函数调用另一个递归函数 fooB。当我想返回时，我继续使用 exit(1) 来停止执行。当递归树很深时，正确的退出方式是什么？

通过递归堆栈返回可能没有帮助，因为返回通常会清除我构建的部分解决方案，而我不想这样做。我想从 main() 执行更多代码。

我读过Exceptions can be used，如果我能得到一个代码片段就好了。

4

2 回答 2

14

这goto语句不能从一个函数跳回另一个函数；Nikos C. 是正确的，它不会考虑释放你所做的每个调用的堆栈帧，所以当你到达你去的函数时，堆栈指针将指向堆栈帧你刚才的功能......不，那是行不通的。同样，您不能简单地调用（直接或间接通过函数指针）您想要在算法完成时结束的函数。在深入研究递归算法之前，您永远不会回到您所处的环境。您可以通过这种方式构建系统，但本质上，每次这样做都会“泄漏”当前堆栈中的内容（与泄漏堆内存不太一样，但效果相似）。

不，您需要以某种方式返回到调用上下文。在 C++ 中只有三种方法可以做到这一点：

  1. 依次退出每个函数，通过调用链以有序的方式从它返回给它的调用者。
  2. 抛出一个异常并在你启动递归算法后立即捕获它（它会以有序的方式自动销毁堆栈上每个函数创建的任何对象）。
  3. 使用 setjmp() 和 longjmp() 来做类似抛出&捕获异常的事情，但是“抛出”一个 longjmp() 不会破坏堆栈上的对象；如果任何此类对象拥有堆分配，则这些分配将被泄露。

要执行选项 1，您必须编写递归函数，以便一旦达到解决方案，它会向其调用者返回某种指示它已完成（可能是相同的函数），并且其调用者会看到该事实并转发通过返回给它的调用者（可能是同一个函数），依此类推，直到最终释放递归算法的所有堆栈帧，然后您返回到调用递归算法中第一个函数的任何函数。

要执行选项 2，您将对递归算法的调用包装在 a 中try{...}，然后在它之后立即出现catch(){...}预期的抛出对象（这可能是计算的结果，或者只是一些让调用者知道“嘿，我是完成，您知道在哪里可以找到结果”）。例子：

try
{
    callMyRecursiveFunction(someArg);
}
catch( whateverTypeYouWantToThrow& result )
{
    ...do whatever you want to do with the result,
    including copy it to somewhere else...
}

...在您的递归函数中，当您完成结果时，您只需：

throw(whateverTypeYouWantToThrow(anyArgsItsConstructorNeeds));

要执行选项 3...

#include <setjmp.h>
static jmp_buf jmp; // could be allocated other ways; the longjmp() user just needs to have access to it.
    .
    .
    .
if (!setjmp(jmp)) // setjmp() returns zero 1st time, or whatever int value you send back to it with longjmp()
{
    callMyRecursiveFunction(someArg);
}

...在您的递归函数中，当您完成结果时，您只需：

longjmp(jmp, 1); // this passes 1 back to the setjmp().  If your result is an int, you
                 // could pass that back to setjmp(), but you can't pass zero back.

使用 setjmp()/longjmp() 的坏处在于，如果在调用 longjmp() 时堆栈上仍有任何堆栈分配的对象仍然“活动”，则执行将跳回 setjmp() 点，跳过析构函数对于那些对象。如果您的算法仅使用 POD 类型，那不是问题。如果您的算法使用的非 POD 类型不包含任何堆分配（例如来自malloc()或new）。如果您的算法使用包含堆分配的非 POD 类型，那么您只有使用上面的选项 1 和 2 才是安全的。但是，如果您的算法符合 setjmp()/longjmp() 的标准，并且如果您的算法在完成时被大量递归调用所掩盖，那么 setjmp()/longjmp() 可能是最快的返回方式到初始调用上下文。如果这不起作用，就速度而言，选项 1 可能是您最好的选择。选项 2 可能看起来很方便（并且可能会在每次递归调用开始时消除条件检查），但与系统自动展开调用堆栈相关的开销有些显着。

通常说您应该为“异常事件”（预计非常罕见的事件）保留异常，而与展开调用堆栈相关的开销就是原因。较旧的编译器使用类似于 setjmp()/longjmp() 的东西来实现异常（setjmp() 在try&的位置catch，longjmp() 在 a 的位置throw），但当然有额外的开销与确定什么对象相关堆栈上需要销毁，即使没有这样的对象。另外，每次遇到 a时try，它都必须保存上下文以防万一throw，如果异常是真正的异常事件，那么保存该上下文所花费的时间就被浪费了。较新的编译器现在更有可能使用所谓的“零成本异常”（也称为基于表的异常），这似乎可以解决世界上所有的问题，但它并没有......它使正常运行时更快，因为不再需要在每次运行时保存上下文 a try，但如果 athrow执行，现在与解码存储在大量表中的信息相关的开销更大，运行时必须处理这些表才能弄清楚如何根据堆栈所在的位置展开堆栈throw遇到和运行时堆栈的内容。所以例外不是免费的，尽管它们非常方便。你会在互联网上找到很多东西，人们声称它们的价格是多么的不合理，它们会减慢你的代码速度，你还会发现很多人驳斥这些说法，双方都提出了艰难的看法数据来支持他们的主张。您应该从参数中得到的好处是，如果您希望它们很少发生，那么使用异常是很好的，因为它们会产生更清晰的接口和逻辑，而无需在每次进行函数调用时对“坏”进行大量条件检查。但是您不应该使用异常作为调用者与其被调用者之间正常通信的手段，

于 2012-12-09T04:49:37.307 回答
1

这在我找到从根到二叉树节点的路径时发生在我身上。我正在使用堆栈来按顺序存储节点，并且递归不会停止，直到最后一个节点返回 NULL。我使用了一个全局变量，整数 i=1，当我到达我正在寻找的节点时，我将该变量设置为 0 并使用 while(i==0) 返回堆栈；允许程序在不弹出我的节点的情况下备份内存堆栈。

于 2014-11-09T22:06:12.027 回答