recursion - 递归和迭代之间的区别

Question

有什么不同？这些是一样的吗？如果没有，有人可以给我一个例子吗？
兆瓦:
迭代 - 1 : 迭代或重复的 Action 或过程或直到满足条件
递归 - 3:一种计算机编程技术，涉及使用一个或多次调用自身直到满足指定条件的过程、子例程、函数或算法，此时每次重复的其余部分从最后一次调用到首先

Answer 1

我们可以将递归和迭代过程与 recursive and iterative processes 区分开来(就像在 SICP 中所做的那样)。 .前者如您的定义所述，其中递归与数学 recursion 基本相同: 一个 recursive procedure是根据自身来定义的。迭代过程使用循环语句重复代码块。然而，递归过程需要非常量(例如 O(n) or O(lg(n)) space )来执行，而迭代过程需要 O(1)(常数)空间。

对于数学示例，斐波那契数是递归定义的:



Sigma notation类似于迭代:



原样 Pi notation .类似于如何将一些(数学)递归公式重写为迭代公式，一些(但不是全部)递归过程具有迭代等价物。通过在您自己的数据结构中跟踪部分结果，而不是使用函数调用堆栈，所有递归过程都可以转换为迭代过程。