如何确定在特定程序中使用递归还是迭代更好？

Question

在我的大学里，我被要求为斐波那契数列写一个JAVA程序。我使用递归来编写这个程序。

但是，助教讲师说我的算法不够高效，并要求我进行分析。他补充说，按照惯例，迭代比递归更适合在该程序中使用。

如何分析我们的算法？如何检查迭代和递归的空间和时间复杂度？就在那时，我发现这些东西和程序的正确性一样重要。

- Dale Steyn

---

如果您使用整数或长整数，您将不会超过60或70次递归，因此并不重要。您也可以使用递归方法缓存结果。 - assylias

同时，递归还是循环？ - nawfal

Answer 1

作为一个规则: - 递归对人类来说很容易理解。但它是基于堆栈的，而堆栈始终是有限的资源。 - 迭代是一种顺序执行的方式，并且同时更容易调试。但有时会导致难以理解的算法，这些算法可以通过递归轻松完成。

因此，每当步骤数被限制在小而可管理的数量时，您可以选择递归。因为您将确信堆栈永远不会溢出，同时递归代码也非常简洁优雅。

如果您想了解更多，这些可能会有所帮助。 递归与循环以及 递归或迭代？ 编辑 正如@MrP所指出的那样，一些特殊的递归可以通过一些编译器进行优化。

- rocketboy

---

只是一句话：递归并不总是基于堆栈的。一些编译器会优化尾递归，使其实际上成为迭代。但当然不能总是依赖这一点。 - MrP

@MrP 说得对，但就像你所说的：a）“一些”编译器 - 不是所有的，b）即使一个支持尾递归优化的编译器也不能为任何递归实现它。好评论！ - Nir Alfasi

谢谢。我刚刚找到了前七项的序列。因此，在这两种方法的难度上没有发现太大的区别。但是，如果您愿意，能否向我解释一下您的观点，“递归代码紧凑而优雅”？ - Dale Steyn

Answer 2

算法的复杂度与此无关: 当您使用递归时，每次调用都会在堆栈上创建一个新框架-因此，如果递归太深，则可能遇到堆栈溢出：)

通过使用迭代-您正在循环运行（潜在地）相同的空间（覆盖参数以前的值），这更快，从StackOverflow角度来看也更安全。

- Nir Alfasi

Answer 3

我建议你跟随链接http://nptel.iitm.ac.in/courses.php?disciplineId=106，寻找一些关于算法设计和分析的课程讲座。这是算法设计非常基础的概念。祝你好运。

- Jatin Malwal

Answer 4

斐波那契数列的最大问题在于算法的时间复杂度。当使用简单递归时，您将不断重新计算所有内容并做很多重复工作。这是因为当您使用递归计算fib(n)时，会重复计算fib(n-1)和fib(n-2)。

int fib(int n) {
  if (n < 2) { return 1; }
  return fib(n-1) + fib(n-2)
}

你将计算fib(n-1)，这将计算fib(n-2)和fib(n-3)。但是为了计算fib(n)，你将已经计算了fib(n-2)。为了改进此问题，您需要存储临时结果。通常使用迭代更容易，并从i = 0开始逐步增加到n。这样，您可以轻松存储最后两个结果并避免重复计算相同的值。

一个判断算法效率的简单方法是尝试解决一些越来越难的例子，你也可以更精确地计算。以斐波那契数列为例。调用fib(n)需要复杂度O(fib(n)) = O(fib(n-1)) +O(fib(n-2)) + 1（我们只考虑加法的复杂度为1）。假设O(fib(0)) = O(fib(1)) = 1，这意味着O(fib(2)) = 3, O(fib((3)) = 5, O(fib(4)) = 9。正如你所看到的，这个系列增长得比斐波那契数列本身还要快！这意味着复杂性会大大增加。如果你有一个从0到n的for循环的迭代算法，你的复杂度将按照n的顺序缩放，这将好得多。

欲了解更多信息，请查看大O符号。

- MrP

---

好的。谢谢，你能推荐一些关于大O符号的阅读链接或参考资料吗？ - Dale Steyn

我找到了维基百科的文章。请问有关于算法设计和分析技术的任何来源吗？ - Dale Steyn

Steven S. Skiena的《算法设计手册》以及Thomas H. Cormen的《算法导论》都非常不错。它们包含了关于良好算法设计和性能问题的信息。 - MrP