在C语言中，什么是跳出递归的惯用方法？

Question

假设我们有一个递归函数f，如果输入不正确，则可能会失败。只能在f运行时检测到输入错误。

在C中，通常的方法是什么来在发生错误时直接从f()中断返回到原始调用函数？

setjmp / longjmp是此处的惯用解决方案吗？

玩具示例：

void g() {
    int arr[] = {1, 2, -3, 4};
    int result = f(0, sizeof(arr)/sizeof(int) - 1, arr);

    /* if f() was successful: */
    printf("%d\n", ); 
    /* if error occurred in f: do something else */
}

int f(int n, int i, int *arr) {
    if (i < 0)
        return n;
    /*
    if (arr[i] < 0) <-- "erroneous input"
        break to g()
    */
    return f(arr[i] + n, i-1, arr);
}

- Szabolcs

---

如果 if(arr[i]<0) return g(); 不起作用，或者返回一些特殊值（如 -1），并在调用函数中处理它呢？ - user684934

f() 已经从 g() 被调用，所以 OP 想要回到调用者。 - Chowlett

Answer 1

以下是选项：

1. 从f()返回一个状态标志，指示成功或失败。这会导致错误从发生错误的深度一级一级地上升，因此可能不是您想要的。请注意，如果您需要解开任何分配或释放资源，f()每个级别都可能会声明，则这是唯一安全的选项。

2. 使用setjmp()和longjmp()来模拟抛出异常并直接跳转到错误处理代码，就像您建议的那样。

- Graham Borland

Answer 2

通常的方式是返回一个表示错误的值，大多数情况下使用-1。

- Jan Henke

---

不知道是谁给你评了分，但如果你稍微改动一下代码，你的答案就能起作用，也就是说，如果（arr[i]>0），则返回-1。在g()中，您可以检查结果是否为-1，这样您就知道函数已经失败了。 - PAntoine

Answer 3

我认为longjmp是可行的方法。但我不会认为这是良好的编码风格。

如果你在代码中开始引入跳转，那么很难看清楚你的代码在做什么。此外还有很多问题：

• 代码可读性下降
• 只能从一个地方调用函数，因此代码的复用性受到严重限制
• 使用longjmp时很容易引入内存泄漏
• 生成的代码更加脆弱（例如，在setjmp之上引入某些代码时很容易出现错误）

除非你有非常特定的性能要求，否则尽量避免使用它，而是让错误结果向下传递给原始调用者。

- jupp0r

---

你为什么认为这不是一个好的编程风格？你可以给出一些可能出错的例子吗？我需要注意哪些方面？ - Szabolcs

谢谢。我认为你所说的“你只能从一个地方调用函数”是指f（在我的例子中）只能从g中调用。这不是问题，因为g是应该实际使用的f接口。f只是方法的“内部”实现。 - Szabolcs

是的，这就是我想说的。您还可以使用一些包装函数，该函数仅包括函数调用和setjmp。我并不是说您不应该这样做，我的观点只是您需要有一个理由这样做，并且这种方法很容易被滥用 :) - jupp0r

Answer 4

如果递归深度很大，我认为使用longjmp更有意义。否则，返回将额外花费O(N)的成本（其中N是递归层数），这包括用大量堆栈帧折磨CPU缓存（每个堆栈帧可能是整个缓存行）。

有人会争辩说longjmp是“不好的风格”，我会同意，但使用深度递归已经是更糟糕的风格了...（而且可能会产生更糟糕的影响，比如吹掉你的堆栈并崩溃程序或产生特权泄漏，而不仅仅是看起来丑陋。）

- R.. GitHub STOP HELPING ICE

---

我会注意递归不要太深（例如当深度约为输入大小的对数时，这是可以接受的），并且这对于我的当前应用程序来说不是一个实际问题，但我确实想知道如何避免在堆栈空间耗尽时崩溃。是否有某种实际的防御措施，例如事先检查可用的堆栈空间并基于此限制递归深度？我想这应该是一个单独的问题。 - Szabolcs

唯一的解决方案是避免递归，特别是在深度没有对数限制的情况下。你可以用自己分配内存的类似递归的数据结构替代函数递归，但是当内存耗尽时，你仍然会面临问题，所以我认为最好的方法是尽量避免那些需要大量工作空间的算法，至少在有合理的替代方案时如此。 - R.. GitHub STOP HELPING ICE

区别在于malloc不会崩溃——它只会告诉我没有足够的空间了。当堆栈空间不足时，难道没有类似的安全解决方案吗？我问这个问题是因为说实话，我不知道不同系统上通常有多少堆栈空间可用（因为这个问题通常不会出现）。当然，我可以测量一下（看看在多少递归步骤之后会崩溃），但那只是我的机器。澄清一下：我没有遇到这个实际问题（堆栈空间不足），我只是对此感到好奇。 - Szabolcs

我猜我的回答不够明确。简单来说，没有一种可移植的方法可以知道你有多少堆栈空间可用/剩余。大多数现代系统默认情况下都会分配相当大的堆栈空间，但在除主线程以外的线程中，它有时会小得多（默认情况下）。另一方面，POSIX线程允许您为创建的线程明确请求特定的堆栈大小，但即使如此，您也不知道编译器将在调用帧开销等方面浪费多少空间... - R.. GitHub STOP HELPING ICE

因此，最好始终尽量减少使用堆栈空间的数量，并让现代系统通常提供大量堆栈空间的事实作为“安全网”，以确保您的程序永远不会因为堆栈溢出而崩溃。 - R.. GitHub STOP HELPING ICE