停止回溯算法

Question

在C/C++中，是否有一种方法可以停止回溯算法，在找到第一个解之后而不退出程序。

我希望我的函数能够立即退出函数，而不是逐层递归地声明返回语句。

- John Retallack

---

C和C++是非常不同的编程语言。你正在使用哪一种？ - Mark Byers

我正在使用C++，但我同时对C和C++感兴趣。 - John Retallack

通常回溯算法处理某些树的高度，递归并不是非常“深入”。也许微优化不会使您的程序更有效率。 - Nick Dandoulakis

你可以使用“异常模式”，即抛出一个无意义的异常，在递归函数外部捕获。 - fredoverflow

Answer 1

一个快速而不太优雅的方法是抛出异常并在基础级别捕获它（现在很多人会尖叫只应该在错误时使用异常，但我认为找到解决方案是一个特殊事件，因为找不到解决方案才是常态）。

- Lie Ryan

---

我很惊讶这些年来这个问题没有得到更多的赞同。这绝不是“草率”的解决方案。它是所述问题的唯一正确解决方案。这种模式在其他语言中非常普遍。抛出自定义异常是清理堆栈并安全地继续的唯一方法，因为只有编译器知道如何完成这项任务。 - Anders

Answer 2

如果你有一个标志，在完成时设置，然后在函数中进行检查，你可以解决这个问题。例如：

void foo(..)
{
   if (g_done) return;
...
}

- AndersK

Answer 3

如果您不确定需要什么，我建议您实现自己的堆栈，并完全避免使用递归。这样退出回溯树变得非常简单（只需一个“return”），并且还可以通过再次调用函数来恢复搜索以查找下一个解决方案，假设用户定义的堆栈状态被保留（在静态变量中）。当然，将简单的递归程序转换为循环需要一些编程开销，但这很容易做到。

- Nathan

---

管理自己的堆栈容易出错，除非您需要挤出最后一点性能，否则将自然递归算法混淆为迭代算法几乎没有任何好处。 - Lie Ryan

假设不需要重复使用堆栈，我认为从递归和返回的角度来看，分配/释放堆栈并不更有效率。 - Nick Dandoulakis

使用自己的堆栈，您可以预先分配最大深度，避免遇到堆栈溢出，避免存储返回地址，避免存储不需要在递归调用中保留的本地变量，避免方法序言/尾声，使优化器更容易处理，可以存储快照并稍后继续，而且 - 如上所述 - 可以随时停止任何深度。这通常需要更多的代码，但对于不理解递归的读者来说更容易分析，可以提供更好的调试和诊断，并且这是一种常见的代码转换，有时会变得必要。 - peterchen

Answer 4

实际上这取决于你的实现方式，但你可以设置一些特殊参数并将其用作标志，例如“我们是否已经得到了解决方案？如果是，则中止当前例程并仅将该解决方案输出”。

- M. Williams

---

如何中止例程？如果使用“return”，它仅会退出当前递归级别。 - John Retallack

那么使用异常处理的方法可能是最好的，但我相信你可以构建你的应用程序，使得“如果我们找到了第一个解决方案，那么我们只需要通过一个return退出每个递归级别。这将被编译器优化，性能甚至比exception方法更好（异常处理会调用堆栈展开，因此在非异常处理方面不应使用，因为它很慢）。 - M. Williams

请原谅我如果我说错了，因为我从未广泛使用过C/C++，但是从函数调用堆栈返回也涉及堆栈展开，对吗？ - Lie Ryan

你是否实际测量过性能并知道它是一个问题？最佳实践是在分析表明存在问题之前避免优化。如果确实存在问题，您应该考虑另一种方法（例如有限状态机）。 - Chris Hafey

我非常确定你永远不会达到“那么深”的程度，你会感受到差异。打开优化通常会折叠那些“return-return-return…”块，一切都会很好。如果你不相信我，你可以简单地使用profile标志方法和异常/longjmp方法。 - M. Williams

Answer 5

为什么你想让函数立即退出呢？不通过堆栈回溯是很危险的，因为可能存在需要销毁的对象。抛出异常可能会解决你的问题，并清理堆栈。提供更多关于你尝试做什么的信息，我们可能能够提供其他方法。

- Chris Hafey

Answer 6

首先，注意并非所有递归函数都可以这样做。 考虑以下代码：

int SumNum(int nMax)
{
    if (0 == nMax)
        return 0;
    else
        return nMax + SumNum(nMax-1);
}

实际值是在回溯过程中计算的。

但是，您可以按照以下方式重写代码：

int SumNum(int nMax, int nSum)
{
    if (0 == nMax)
        return nSum;
    else
        return SumNum(nMax-1, nSum+nMax);
}

现在，你可以做以下的技巧：

    int SumNum(int nMax, int nSum)
    {
        if (0 == nMax)
            throw nSum;
        else
            return SumNum(nMax-1, nSum+nMax);
    }


f()
{
        int nSum;

        try
        {
            SumNum(100, 0);
        }
        catch (int _nSum)
        {
            nSum= _nSum;
        }
}

- Lior Kogan

Answer 7

你可以在C和C++中使用setjmp()/longjmp()，以一种简单但有效的方式绕过需要将标志传递回去的需求。

- Richard Pennington

---

我认为在C++中不应该使用setjmp和longjmp。 - M. Williams

它应该被非常小心地使用，longjmp会绕过析构函数的调用。但速度确实无法匹敌。 - Hans Passant

它们可能永远不应该被使用（因此有了粗糙但有效的注释），但它们确实存在并且可以（小心地！）在C和C++中使用。 - Richard Pennington

Answer 8

如果你的回溯算法真的递归得够深，那么你不应该使用递归，因为你可能会危及堆栈。与其犯下一些涉及longjmp的暴行，你应该考虑将算法重写为迭代方法，并使用自己的堆分配的堆栈，其中存储表示状态的POD对象。当你找到解决方案时，状态容器可以在一步中被销毁，答案可以返回。

参见从递归到迭代的方法。

- Alan