如果我们使用循环而不是递归,或者反之,在两者都可以达到相同目的的算法中,性能是否会受到影响?检查给定的字符串是否是回文。 我见过许多程序员使用递归作为一种炫耀的手段,当一个简单的迭代算法可以满足要求。 编译器在决定使用什么时起着至关重要的作用吗?
当前回答
迈克说得对。Java编译器或JVM没有优化尾部递归。你总是会得到这样的堆栈溢出:
int count(int i) {
return i >= 100000000 ? i : count(i+1);
}
其他回答
Your performance deteriorates when using recursion because calling a method, in any language, implies a lot of preparation: the calling code posts a return address, call parameters, some other context information such as processor registers might be saved somewhere, and at return time the called method posts a return value which is then retrieved by the caller, and any context information that was previously saved will be restored. the performance diff between an iterative and a recursive approach lies in the time these operations take.
从实现的角度来看,当处理调用上下文所需的时间与执行方法所需的时间相当时,您才真正开始注意到差异。如果递归方法的执行时间比调用上下文管理部分要长,那么就采用递归方法,因为代码通常更易于阅读和理解,而且不会注意到性能损失。否则,出于效率考虑,可以进行迭代。
堆栈溢出只会发生在编程语言没有内置内存管理....否则,请确保在函数(或函数调用、STDLbs等)中有一些内容。如果没有递归,就不可能有这样的东西……谷歌或SQL,或任何地方一个人必须有效地排序大型数据结构(类)或数据库。
如果你想要遍历文件,递归是一种方法,我敢肯定这就是find * | ?grep *的工作方式。有点像双重递归,特别是管道(但不要像很多人那样做一堆系统调用,如果你要把它放在那里供别人使用的话)。
高级语言,甚至clang/cpp也可以在后台实现相同的功能。
递归有一个缺点,使用递归编写的算法的空间复杂度为O(n)。 而迭代方法的空间复杂度为O(1)。这是使用迭代而不是递归的优点。 那我们为什么要用递归呢?
见下文。
有时使用递归编写算法更容易,而使用迭代编写相同的算法略难。在这种情况下,如果您选择遵循迭代方法,您将不得不自己处理堆栈。
你必须记住,使用太深的递归,你会遇到堆栈溢出,这取决于允许的堆栈大小。为了防止这种情况,请确保提供一些基本情况,以结束递归。
通常情况下,人们会期望性能损失在另一个方向上。递归调用会导致构建额外的堆栈帧;对此的惩罚各不相同。此外,在一些语言中,如Python(更准确地说,是在某些语言的某些实现中……),对于递归指定的任务,您可能很容易遇到堆栈限制,例如在树状数据结构中查找最大值。在这些情况下,你应该坚持使用循环。
编写好的递归函数可以在一定程度上降低性能损失,前提是你有一个优化尾部递归的编译器,等等(还要再次检查,确保函数真的是尾部递归——这是许多人都会犯的错误之一)。
除了“边缘”情况(高性能计算、非常大的递归深度等)之外,最好采用最清楚地表达您的意图、设计良好且可维护的方法。仅在确定需求后进行优化。
推荐文章
- 为什么引入无用的MOV指令会加速x86_64汇编中的紧循环?
- 哪些是遗传算法/遗传规划解决方案的好例子?
- 如何在SQL中有效地计数列值的发生?
- 使用curl在PHP中获取HTTP代码
- 确定PHP中是否存在数组键的更快更好的方法是什么?
- 如何在O(n)中找到长度为n的无序数组中的第k大元素?
- 匿名递归PHP函数
- 一个用于膨胀/收缩(抵消,缓冲)多边形的算法
- postgresql COUNT(DISTINCT…)非常慢
- 我如何使用Node.js Crypto创建HMAC-SHA1哈希?
- 对于不可变集合上的非突变“add”方法,最好的名称是什么?
- 如何用动态规划确定最长递增子序列?
- 在c++程序中以编程方式检测字节序
- 理解递归
- foo到底是什么意思?