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

Question

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

我从事机器学习/数据挖掘,因此让我的代码可扩展是非常关键的.

当我使用Java时,我尽可能避免使用递归调用,因为我经常让我的调用堆栈溢出.虽然有控制分配给调用堆栈的内存量的选项,但我认为让我的程序依赖于较少数量的参数是更理想的.因此,当很清楚如何在没有递归调用的情况下实现,可能使用自己管理的堆栈,我这样做了.但即使在Java中,我也不确定这是一门正确的学科.

据我所知,C/C++中没有调用堆栈,所以我不担心溢出它.因此,我很好奇:在程序的可伸缩性方面,是否会尝试避免使用递归,或者是鼓励它,还是特定于问题？

Answer 1

这个问题没有一个正确的答案.对于某些问题,递归效果很好.对于其他人,它没有.

据我所知,C/C++中没有调用堆栈

只是要清楚,这是不正确的:有是在C和C的所有实现++,我知道的调用堆栈.

Answer 2

据我所知,C/C++中没有调用堆栈,所以我不担心溢出它

咦？当然,标准没有讨论调用堆栈,但实际上在大多数(如果不是全部)实现中都有一个.

现在,应该避免递归吗？首先,众所周知,每个递归函数都可以迭代重写(即没有递归).而且,有时迭代解决方案比递归解决方案更快.但是对于某些任务,例如图中的DFS,递归是如此简单和有用,除非你有充分的理由不这样做,否则你不应该避免使用它.同一个DFS的迭代解决方案几乎一样简单,但需要更多的输入......

我的2 c.

Answer 3

C 和 C++ 中的调用堆栈在某一方面有点像 C++ 中的 vtable - 据我所知，标准中没有提到它，即，没有强制执行该实现，但出于所有实际目的，它几乎总是这样实现方式。

当然，有一些深奥的架构，特别是在嵌入式世界中，可能会避开堆栈。PIC 是堆栈不友好架构的一个例子，一些微型微控制器不支持堆栈，至少不直接支持。在某些情况下，无论如何都可以消除堆栈的使用（内联函数或函数调用的积极优化，使用寄存器作为局部变量而不是堆栈空间）。

无论如何，对于你的问题......这是一个非常主观的问题，通常可以归结为一个问题：你买得起吗？

如果您有足够的堆栈空间，并且递归的深度不足以破坏您的堆栈，那么递归通常是正确的选择。不总是，但经常。

但你必须了解你的架构、平台、工具集等，并知道你的堆栈有多大。例如，对于许多多任务嵌入式系统，堆栈大小是在创建线程/任务时确定的，并且不会“根据需要增长”。其他简单（嵌入式）系统仅使用单个堆栈，或者可能是一个“后台”堆栈和一个中断堆栈。还有一些允许堆栈根据需要在限制内增长，具体取决于处理器和操作系统。

如果您有 Java 背景，那么如果这种讨论对您来说是陌生的，我不会感到惊讶。