退出整个递归堆栈

Question

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

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

我读过可以使用Exceptions,如果我能获得代码片段会很好.

Answer 1

该goto声明无法从一个函数跳回到另一个函数; Nikos C.是正确的,它不会考虑释放你所做的每个调用的堆栈帧,所以当你到达你转到的函数时,堆栈指针将指向堆栈帧你刚才的功能......不,那是行不通的.类似地,您不能简单地调用(直接或间接通过函数指针)您想要在算法完成时结束的函数.在深入了解递归算法之前,你永远不会回到你所处的环境.你可以想象用这种方式构建一个系统,但实际上每次你这样做都会"泄漏"当前堆栈上的内容(与泄漏堆内存不同,但效果类似).如果你深入到一个高度递归的算法,那可能是很多"泄露"的堆栈空间.

不,你需要以某种方式返回到调用上下文.在C++中只有三种方法可以实现:

1. 通过从有序方式通过调用链向其调用者返回来依次退出每个函数.
2. 抛出异常并在启动到递归算法后立即捕获它(它会以有序的方式自动销毁堆栈上每个函数创建的任何对象).
3. 使用setjmp()和longjmp()来执行类似于抛出和捕获异常的操作,但是"抛出"longjmp()不会破坏堆栈上的对象; 如果任何此类对象拥有堆分配,那么这些分配将被泄露.

要执行选项1,您必须编写递归函数,以便一旦达到解决方案,它就会返回某种指示,表明它已完成其调用者(可能是相同的函数),并且其调用者会看到该事实并继续执行事实上,通过返回它(可能是相同的函数)来调用它,依此类推,直到最后所有递归算法的堆栈帧都被释放,然后你返回到递归算法中称为第一个函数的任何函数.

要做选项2,你将调用包装到你的递归算法中,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类型不包含任何堆分配(例如from malloc()或new),这也不是问题.如果您的算法使用包含堆分配的非POD类型,那么您只能安全使用上面的选项1和2.但是如果你的算法符合使用setjmp()/ longjmp()的标准,并且你的算法在它完成的时候被埋在大量的递归调用之下,那么setjmp()/ longjmp()可能是最快的回归方式到初始调用上下文.如果这不起作用,选项1可能是你速度方面最好的选择.选项2看似很方便(并且可能会在每次递归调用开始时消除条件检查),但与系统自动展开调用堆栈相关的开销有些重要.

通常会说您应该为"异常事件"(预期非常罕见的事件)保留异常,并且与展开callstack相关的开销是原因.旧的编译器使用一个类似于对setjmp()/ longjmp的()来实现异常(的setjmp()的位置try和catch,和longjmp()在的位置throw),但有以判断哪些对象相关课程的额外开销在堆栈上需要销毁,即使没有这样的对象.另外,每次遇到a时try,都必须保存上下文以防万一有throw,如果异常是真正特殊的事件,那么节省上下文的时间就会浪费掉.较新的编译器现在更有可能使用所谓的"零成本异常"(又名基于表的异常),这似乎可以解决所有世界的问题,但它不会......它使正常的运行时更快,因为每次运行时都不再需要保存上下文try,但是在throw执行的情况下,现在存在与解码存储在大型表中的信息相关的更多开销,运行时必须处理这些信息以便弄清楚如何根据throw遇到的位置和运行时堆栈的内容来展开堆栈.因此异常并非免费,即使它们非常方便.你会在互联网上找到很多东西,人们会在这些东西上声称他们的代价是多么昂贵,以及他们减慢代码的速度,你也会发现许多人反驳这些说法,双方都很努力数据来支持他们的主张.您应该从参数中获取的是,如果您希望它们很少发生,则使用异常会很好,因为它们会产生更清晰的接口和逻辑,每次进行函数调用时都没有大量条件检查"不良".但是,您不应该使用异常作为调用者与其被调用者之间正常通信的方式,因为这种通信方式比仅使用返回值要昂贵得多.