时间戳

首页 > 解决方案 > 递归函数何时优于其迭代版本？

function - 递归函数何时优于其迭代版本？

问题描述

众所周知，每个递归函数都可以在迭代版本中实现。

但是，递归函数通常在堆栈管理方面有一些开销。

考虑到这一点，我想知道是否有一般原则允许我们决定递归版本何时优于给定函数的迭代版本，假设两者具有相同的时间复杂度。

标签： functionrecursion

解决方案

虽然与调用相同函数的循环相比，递归函数可能有一些额外的开销，但除此之外，两种方法之间的差异相对较小。

选择递归而不是迭代方法的主要驱动因素是要解决的问题的复杂性（即运行时间）。迭代大大击败递归的典型例子是斐波那契数列。

使用递归计算第五个斐波那契数需要计算：

f(5) = f(4) + f(3)
   f(4) = f(3) + f(2)
        f(3) = f(2) + f(1)
   f(3) = f(2) + f(1)

以上需要四次递归调用和大约 10 次函数评估。另一方面，如果我们改为使用动态规划并迭代地构建斐波那契，我们将只需要两个函数调用（两者f(1)都是f(2)1 的常量值）：

f(3) = f(2) + f(1) (first call)
f(4) = f(3) + f(2) (second call)

当计算较大的斐波那契数列值时，使用迭代的优势变得更加明显，例如f(100)，递归通过堆栈溢出爆炸。

推荐阅读