如果我们使用循环而不是递归,或者反之,在两者都可以达到相同目的的算法中,性能是否会受到影响?检查给定的字符串是否是回文。 我见过许多程序员使用递归作为一种炫耀的手段,当一个简单的迭代算法可以满足要求。 编译器在决定使用什么时起着至关重要的作用吗?
当前回答
这取决于“递归深度”。 这取决于函数调用开销对总执行时间的影响程度。
例如,用递归的方式计算经典阶乘是非常低效的,因为: —数据溢出风险 -栈溢出风险 —函数调用开销占执行时间的80%
同时开发一种最小-最大算法用于国际象棋游戏中的位置分析,该算法将分析后续的N步棋,可以在“分析深度”上以递归方式实现(正如我正在做的^_^)
其他回答
递归在某些情况下非常有用。例如,考虑查找阶乘的代码
int factorial ( int input )
{
int x, fact = 1;
for ( x = input; x > 1; x--)
fact *= x;
return fact;
}
现在用递归函数来考虑这个问题
int factorial ( int input )
{
if (input == 0)
{
return 1;
}
return input * factorial(input - 1);
}
通过观察这两个,我们可以看到递归很容易理解。 但如果不小心使用,它也会很容易出错。 假设如果我们错过了if (input == 0),那么代码将执行一段时间,并以堆栈溢出结束。
你必须记住,使用太深的递归,你会遇到堆栈溢出,这取决于允许的堆栈大小。为了防止这种情况,请确保提供一些基本情况,以结束递归。
这取决于语言。在Java中,你应该使用循环。函数式语言优化递归。
使用递归,每次“迭代”都会产生函数调用的成本,而使用循环,你通常只需要支付递增/递减的代价。因此,如果循环的代码并不比递归解决方案的代码复杂多少,循环通常会优于递归。
把它写成递归,或者作为练习,可能会很有趣。
但是,如果要在生产中使用该代码,则需要考虑堆栈溢出的可能性。
尾递归优化可以消除堆栈溢出,但是您是否想要经历这样的麻烦,并且您需要知道您可以指望它在您的环境中进行优化。
每次算法递归,数据大小或n减少了多少?
If you are reducing the size of data or n by half every time you recurse, then in general you don't need to worry about stack overflow. Say, if it needs to be 4,000 level deep or 10,000 level deep for the program to stack overflow, then your data size need to be roughly 24000 for your program to stack overflow. To put that into perspective, a biggest storage device recently can hold 261 bytes, and if you have 261 of such devices, you are only dealing with 2122 data size. If you are looking at all the atoms in the universe, it is estimated that it may be less than 284. If you need to deal with all the data in the universe and their states for every millisecond since the birth of the universe estimated to be 14 billion years ago, it may only be 2153. So if your program can handle 24000 units of data or n, you can handle all data in the universe and the program will not stack overflow. If you don't need to deal with numbers that are as big as 24000 (a 4000-bit integer), then in general you don't need to worry about stack overflow.
但是,如果每次递归时都将数据或n的大小减小一个常数,那么当n仅变为20000时,就会遇到堆栈溢出。也就是说,当n为1000时,程序运行良好,你认为程序很好,然后在未来的某个时候,当n为5000或20000时,程序堆栈溢出。
所以如果你有堆栈溢出的可能,试着让它成为一个迭代的解决方案。
推荐文章
- 如何有效地从数组列表或字符串数组中删除所有空元素?
- 在SQL Server上使用varchar(MAX) vs TEXT
- 就地基数排序
- .toArray(new MyClass[0]) or .toArray(new MyClass[myList.size()])?
- 是什么导致JNI调用变慢?
- 检查属性是否有属性
- 如何快速清除JavaScript对象?
- 投弹算法
- 排序10个数字的最快方法?(数字为32位)
- Node.js vs .Net性能
- 如果使用if-return-return或if-else-return?
- 数组与链表
- 为什么MYSQL的高LIMIT偏移量减慢查询?
- SQL JOIN vs IN性能?
- 计算趋势主题或标签的最佳方法是什么?