本文简单比较了一下相同逻辑下,递归实现和循环实现的效率差异
已经不记得最初是从哪里获取的信息了,自己总有一个印象是递归的效率比循环差,因为递归有很大的函数调用开销,再加上递归可能存在的堆栈溢出问题...简单举个加法的例子(求解前 n 个自然数的和):
// C#
// recur version
int AddRecur(int val)
{
if (val > 0)
{
return val...其实一般而言,栈内存的操作消耗都要小于堆内存的操作消耗,上面例子中引入的(模拟)调用栈其实就是一种堆操作,考虑到 CLR(C#) 的可能影响,我也用 C++ 进行了一样的实现对比,最终结果也是一致的,甚至在...C++ 中实现的循环版本还要显著慢于其递归版本....结论
一般而言,将递归代码改写为循环代码可以提高效率,但是一旦改写过程中引入了堆操作,那么结果往往是相反的.