转载

递归还是迭代

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

先打自己的脸

我单纯的觉得迭代就是递归,或者是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 的阶乘过程，非常符合这个描述；

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

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

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

优缺点

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

参考

http://nxlhero.blog.51cto.com/962631/1231228
https://www.wikiwand.com/zh/%E8%BF%AD%E4%BB%A3
https://www.wikiwand.com/zh/%E9%80%92%E5%BD%92

原文 http://giantming.net/di-gui-huan-shi-die-dai/

正文到此结束

所属分类：编程技术

本文标签： CTO 空间 UI https http 缩小 REST
版权声明： 本文为互联网转载文章，出处已在文章中说明(部分除外)。如果侵权，请联系本站长删除，谢谢。
本文海报： 生成海报一生成海报二

其他链接

关于本站

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。

问题交流

递归还是迭代

先打自己的脸

递归定义

迭代定义

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

举个栗子,计算n阶乘:

计算过程展开

优缺点

参考

热门推荐

相关文章

说给你听

本文目录

随机标签

书籍教程

近期评论

网站信息

其他链接

关于本站

问题交流