在C/C++中是否应该避免使用递归调用？

Question

在C/C++中应该避免使用递归调用函数吗？

我从事机器学习/数据挖掘工作，所以让我的代码可扩展性非常关键。

当我使用Java时，尽可能地避免使用递归调用，因为我经常会遇到调用栈溢出的情况。虽然有选项可以控制分配给调用堆栈的内存量，但我认为使程序依赖于更少的参数更为理想。因此，如果不使用递归调用，而是使用我自己管理的堆栈来实现清晰，我就这样做了。但是我不确定即使在Java中，这是否是正确的纪律。

据我所知，在C/C++中没有调用堆栈，所以我不必担心它会溢出。因此，我很好奇：我们应该尝试避免使用递归，还是鼓励使用，或者这是针对您的程序可扩展性的问题特定解决方案？

- d_ijk_stra

---

C/C++ 中确实存在一个调用栈（call stack）。 - lhf

引用一位匿名的SO用户的话：“你所说的C/C++语言是什么？我只知道C和C++…” - Necrolis

尾递归或isEven/isOdd递归非常适合优化，可以完全消除不断增长的堆栈，因此如果适当，就没有普遍的理由要避免使用它们。 - Kerrek SB

在我的认知里... 以这样一个雄心勃勃的昵称，你应该更加明白，真的。 - sbi

@DeadMG 为什么它是精确定位且具体的硬件依赖？我认为它取决于编译器，这在很大程度上但并非全部受硬件驱动。 - San Jacinto

Answer 1

这个问题没有单一正确的答案。对于某些问题，递归很有效。对于其他问题，它则不是。

就我所知，C/C++ 中不存在调用栈

只是为了澄清，这是错误的：据我所知，所有的 C 和 C++ 实现中都存在调用栈。

- NPE

Answer 2

据我所知，在C/C++中没有调用栈，因此不必担心溢出。

什么？当然，标准并没有讨论调用栈，但是在大多数实现中确实存在调用栈。

那么，递归是否应该避免？首先，众所周知，每个递归函数都可以重写为迭代形式（即不使用递归）。而且，有时候迭代解决方案比递归解决方案更快。但对于某些任务，例如在图中进行DFS，递归非常简单和有用，你不应该避免使用它，除非你有很好的理由不这样做。相同DFS的迭代解决方案几乎同样简单，但需要更多的打字...

我的意见。

- Armen Tsirunyan

---

没错，标准中并没有提及它（除了堆栈展开），而且有很多嵌入式处理器没有堆栈。 - Gene Bushuyev

@Gene：即使提到堆栈展开，标准也不意味着或要求完全使用调用堆栈。它只是说明当抛出异常时清理过程被称为“堆栈展开”。 - R. Martinho Fernandes

这不是好的建议。只有在可以限制递归深度时才应该使用递归DFS遍历图。如果你的图恰好是一个链表，那么很容易就会超出栈的深度。对于许多大型数据集来说，在C/C++中进行递归DFS是一个坏主意。 - Taylor

并非所有的递归函数都可以被迭代地写出来。对于那些可能被使用的函数（即不是数学家编写的奇怪和牵强附会的函数来证明一点），它们要少得多。在绝大多数函数中，你可以自由选择更“清晰”的解决方案（无论你如何定义“清晰”），除非性能或堆栈限制将你朝某个方向推动。 - Ben

@Ben：别担心，当然有部分递归函数不是原始递归的。还有一些函数甚至不是部分递归的，但这些函数无论如何都是不可计算的——根据图灵-丘奇假设，无论是递归还是迭代都不行。 - Armen Tsirunyan

Answer 3

在C和C++中，调用栈有一个方面类似于C++中的虚函数表 - 就我所知，它在标准中没有被提及，也就是说，实现并没有被强制规定，但在实际应用中，它几乎总是以这种方式实现的。当然，有一些奇特的体系结构，特别是在嵌入式领域，可能会避免使用堆栈。PIC就是一个不友好的堆栈体系结构的例子，一些小型微控制器不支持堆栈，至少不是直接支持。在某些情况下，可以通过内联函数或针对函数调用的激进优化，使用寄存器来代替栈空间的局部变量等方式来消除堆栈的使用。

无论如何，对于你的问题...这是一个非常主观的问题，通常归结为一个问题：你能负担得起吗？如果你有足够的堆栈空间，并且递归不会深到足以炸掉你的堆栈，递归通常是正确的选择。但你必须了解你的架构、平台、工具集等，并知道你的堆栈有多大。例如，许多多任务嵌入式系统在创建线程/任务时确定堆栈大小，它不会“按需增长”。其他简单(嵌入式)系统只使用一个堆栈，或者可能有一个“后台”堆栈和一个中断堆栈。还有一些允许堆栈在必要时（在限制范围内）增长，这取决于处理器和操作系统。

如果你来自Java背景，如果这种讨论对你来说是新的，我并不感到惊讶。

- Dan

Answer 4

我经常遇到调用栈溢出的问题。

那是你自己的问题。

递归是一种非常有用的结构，当正确使用时。特别是在需要处理变量大小的数据结构时。限制递归深度很容易：

int recurse(int maxlimit, ...)
{
   if (!--maxlimit) return false; // and throw an exception or something
   ...
   return completed ? finalvalue : recurse(maxlimit, ...);
}

- symcbean

---

如果你需要实际计算什么东西，那么限制递归深度并没有太大的帮助。堆栈空间很小，这种情况下最好使用迭代。 - Taylor

Answer 5

递归可以是表达算法的一种非常优雅的方式。在C/C++中，主要缺点是潜在的堆栈溢出。

以下是C/C++的一个经验法则：

如果递归不是尾调用，则深度需要在数据大小的次线性范围内。

例如，如果你正在递归地进行二叉树的深度优先搜索，那么这棵树必须平衡，以使递归深度为O(log n)。这确保了没有堆栈溢出。不要使用非尾递归来遍历链表（深度为O(n)）。

- Taylor

---

值得注意的是，尽管我知道（至少在某些情况下），最近的GCC会将尾调用递归优化为循环，但C或C ++标准并不保证这一点。 - Jack Lloyd

@JackLloyd 没有任何保证标准中会有堆栈。 - Ludovic Zenohate Lagouardette