神刀安全网

递归还是迭代

还是那本书<冒号课堂>,上看来的,这本书好处就是纠正了我一些错误的认知

先打自己的脸

我单纯的觉得迭代就是递归,或者是for循环 (啪~

递归定义

递归(英语:Recursion),又译为递回,在数学与计算机科学中,是指在函数的定义中使用函数自身的方法.递归一词还较常用于描述以自相似方法重复事物的过程.例如: 当两面镜子相互之间近似平行时,镜中嵌套的图像是以无限递归的形式出现的.也可以理解为自我复制的过程. (wiki)

迭代定义

迭代是重复反馈过程的活动,其目的通常是为了接近并到达所需的目标或结果.每一次对过程的重复被称为一次 "迭代",而每一次迭代得到的结果会被用来作为下一次迭代的初始值. (wiki)

在计算机科学中,迭代是程序中对一组指令(或一定步骤)的重复。它既可以被用作通用的术语(与 “重复” 同义),也可以用来描述一种特定形式的具有可变状态的重复。

看到知乎一个关于这个问题的答案interesting

递归: 】】】 】】】】】】 ... 】】】】】】】】】 】】】】】】】】】】】】 】】】】】】】】】 ... 】】】】】】 】】】  迭代: 】】】 】】】 】】】 】】】 ... 】】】 】 

举个栗子,计算n阶乘:

  • 递归方法求n阶乘
function fact(n) {       if (n === 1) {         return 1;     } else {         return n * fact(n-1);     } } 

这个实现里,函数不断调用自身,所以这是一个迭代,它将一个大规模的问题,不断分解成小的问题进行求解.

  • 迭代代方法
function fact(n) {       function fact_iter(product, count, n) {         if (count > n) {             return product;         } else {             return fact_iter(product*count, count+1, n);         }     }     return fact_iter(1, 1, n); } 

这个实现里,fact_iter也调用了自身,所以,在这种实现里,它是迭代也是递归

  • 上面那个不好理解下面这个也是一样的
function fact(n) {       var result = 1;     for(var i = i; i <= n; i ++) {         result *=i;     }     return result; } 

第三种实现里,它是迭代,但是它并不是递归, 他在循环中对result不断赋值,这种改变赋值—-或者叫做 可变状态 —是迭代的特征

计算过程展开

fact(5); 我们把计算过程展开看看

  • 递归
fact(5);  5 * fact(4);  5 * 4 * fact(3);  5 * 4 * 3 * fact(2);  5 * 4 * 3 * 2 * fact(1);  5 * 4 * 3 * 2 * 1;  20 * 3 * 2 * 1;  60 * 2 * 1;  120 * 1;  120 
  • 迭代
fact(5);  fact_iter(1, 1, 5);  fact_iter(1*1, 1+1, 5);  fact_iter(1*2, 2+1, 5);  fact_iter(2*3, 3+1, 5);  fact_iter(6*4, 4+1, 5);  fact_iter(24*5, 5+1, 5);  120 
  • 循环的迭代方法
fact(5);  result = 1;  result = 1*1;  result = 1*2;  result = 2*3;  result = 6*4;  result = 24*5;  result = 120;  120; 

如你所见递归有一个展开到收缩的过程,而迭代没有.

递归过程中, 问题的规模在缩小,这样最终得到问题的解;而迭代是一种由远变近的逼近,问题的规模不见得缩小了,但是慢慢在调整接近答案。递归求解 n 的阶乘过程,非常符合这个描述;

迭代是逐渐逼近,用新值覆盖旧值,直到满足条件后结束,不保存中间值,空间利用率高。 递归是将一个问题分解为若干相对小一点的问题,遇到递归出口再原路返回,因此必须保存相关的中间值,这些中间值压入栈保存,问题规模较大时会占用大量内存。

所以,以我的理解,函数调用了自身,就是递归.

不断重复一个过程,逐步逼近结果,则是迭代;

优缺点

迭代是在局部内存进行重复计算,递归需要展开栈空间进行每一步的函数现场存储和结果存储。迭代没有这个展开的开销

参考

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » 递归还是迭代

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址