递归和迭代

有什么区别？这些都一样吗？如果没有，有人可以给我一个例子吗？递归和迭代

MW：迭代-1：迭代或重复的动作或过程：作为a：一系列操作的重复产生连续接近期望结果的结果的过程b：重复计算机指令指定次数或直到满足条件

Recusion - 3：涉及使用调用自身一次或多次直到指定条件为止的过程，子例程，函数或算法的计算机编程技术在这段时间里，每次重复的其余部分都从最后一个被调用到第一个处理

2010-04-05 Strawberry

不同之处在于递归为您提供了一个堆栈，无需索取一个堆栈。如果你需要一个，迭代让你问一个。其他一切都是奇怪的。 – CandiedOrange 2017-05-27 04:42:27

我们可以从recursive and iterative processes中区分（如在SICP中完成的）递归和迭代过程。前者与你的定义所描述的一样，其中递归基本上与数学recursion相同：根据其自身定义a recursive procedure。迭代过程用循环语句重复一段代码。但是，递归过程是一个非常量（例如O(n) or O(lg(n)) space）执行，而迭代过程需要O（1）（常量）空间。

对于数学实例中，所述斐波那契数是递归定义：

Fibonacci function

Sigma notation类似于迭代：

$harmonic number$

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

来源

2010-04-05 05:19:45 outis

我喜欢这个答案的大部分，但我不同意递归意味着非恒定空间。 http://en.literateprograms.org/Fibonacci_numbers_%28Scheme%29比较“直接”和尾递归方法。根据上述定义，链接中的尾递归函数不是递归的： -/ – 2010-04-05 23:34:44

@pst：我认为你错过了这一点。使用尾递归的函数是一个递归过程，并生成一个迭代过程。递归进程根据定义使用非恒定空间。 – outis 2010-04-06 01:23:38

@outis：不要让你很好...... 首先你说r＆i PROCEDURES与r＆i PROCESSES不同。一个是空间不变，另一个不是。了解。然后你说迭代过程循环，而迭代过程在空间中是恒定的。 i PROCEDURE和i PROCESS之间的区别是什么？循环可以是恒定的，但不必。 – CoR 2012-06-07 23:39:10

这是一个Lisp函数找到列表的长度。它是递归：

(defun recursive-list-length (L) 
    "A recursive implementation of list-length." 
    (if (null L) 
     0 
    (1+ (recursive-list-length (rest L)))))

它读取“的列表的长度是0，如果该列表为空，或1加开始与所述第二元件的子列表的长度）

而这是strlen的实现 - C函数找到一个空终止char*字符串的长度是迭代：

size_t strlen(const char *s) 
{ 
    size_t n; 

    n = 0; 
    while (*s++) 
     n++; 
    return(n); 
}

你的目标是重复一些操作使用迭代，你雇用一个明确的环（像。 while厕所p代码中的strlen）。使用递归，你的函数使用（通常）更小的参数来调用自己，等等，直到符合边界条件（上面代码中的null L）。这也重复了操作，但没有明确的循环。

来源

2010-04-05 05:02:27

根据你提到的定义，这两个是非常不同的。在迭代中，没有自我调用，但在递归中，函数自己调用

例如。对于阶乘运算

fact=1 
For count=1 to n 
fact=fact*count 
end for

和递归版本

function factorial(n) 
if (n==1) return 1 
else 
n=n*factorial(n-1) 
end if 
end function

迭代算法通常

递归代码更简洁，但使用较大的内存量。有时，递归可以转换为使用dynamic programming.

来源

2010-04-05 05:03:16 Midhat

[快点特朗普这个！]迭代

一种形式可以转换为其他，但有一个明显的限制：许多“流行”的语言（C/Java的/普通的Python）不支持TCO/TCE（tail-call-optimization/tail-call-elimination），因此每次一个方法递归地调用自己时，使用递归会'向堆栈添加额外的数据'。

所以在C和Java中，迭代是惯用的，而在Scheme或Haskell中，递归是惯用的。

来源

2010-04-05 05:07:08

对于上述的一个很好的例子，考虑用于深度优先搜索的递归与迭代过程。它可以通过递归函数调用使用语言特性完成，也可以在使用堆栈的迭代循环中完成，但该过程本身是递归的。

来源

2010-04-05 05:29:20

递归：例如：以斐波那契数列为例。要得到任何斐波那契数字我们必须知道前一个。所以你会在每个小于给定的数字的情况下对相同的操作进行操作（同一个操作），并调用相同的方法。

FIB（5）=蛋白原（4）+ 5

FIB（4）=蛋白原（3）+ 4 。。即重复使用方法fib

迭代循环就像添加1 + 1 + 1 + 1 + 1（迭代添加）以获得5或3 * 3 * 3 * 3 * 3（迭代相乘）以获得3^5。

来源

2010-11-30 10:31:13 Aadishri

针对递归与非递归之间的区别; 递归实现有点更容易验证的正确性; 非递归实现有点效率更高。

Algorithms (4th Edition)

来源

2017-05-27 03:52:56

回答

相关问题