迭代是人,递归是神(迭代与递归的总结:比较)
在计算机编程实现中有常常两种方法:一曰迭代(iterate);二曰递归(recursion)。
从“编程之美”的角度看,可以借用一句非常经典的话:“迭代是人,递归是神!”来从宏观上对二者进行把握。
从概念上讲,递归就是指程序调用自身的编程思想,即一个函数调用本身;迭代是利用已知的变量值,根据递推公式不断演进得到变量新值得编程思想。
从直观上讲,递归是将大问题化为相同结构的小问题,从待求解的问题出发,一直分解到已经已知答案的最小问题为止,然后再逐级返回,从而得到大问题的解(一个非常形象的例子就是分类回归树 classification and regression tree,从root出发,先将root分解为另一个(root,sub-tree),就这样一直分解,直到遇到leafs后逐层返回);而迭代则是从已知值出发,通过递推式,不断更新变量新值,一直到能够解决要求的问题为止。
以斐波那契数列的求解为例,通过两种典型的实现进行对比:
fib(0)=0;
fib(1)=1;
fib(n)=fib(n-1)+fib(n-2);
递归的实现
int fib(int n){ if(n>1) return fib(n-1) + fib(n-2); else return n; // n = 0, 1时给出recursion终止条件 }
int fib(int n){ int i, temp0, temp1, temp2; if(n<=1) return n; temp1 = 0; temp2 = 1; for(i = 2; i <= n; i++){ temp0 = temp1 + temp2; temp2 = temp1; temp1 = temp0; } return temp0; }
递归实际上不断地深层调用函数,直到函数有返回才会逐层的返回,因此,递归涉及到运行时的堆栈开销(参数必须压入堆栈保存,直到该层函数调用返回为止),所以有可能导致堆栈溢出的错误;但是递归编程所体现的思想正是人们追求简洁、将问题交给计算机,以及将大问题分解为相同小问题从而解决大问题的动机。
迭代大部分时候需要人为的对问题进行剖析,将问题转变为一次次的迭代来逼近答案。迭代不像递归一样对堆栈有一定的要求,另外一旦问题剖析完毕,就可以很容易的通过循环加以实现。迭代的效率高,但却不太容易理解,当遇到数据结构的设计时,比如图‘表、二叉树、网格等问题时,使用就比较困难,而是用递归就能省掉人工思考解法的过程,只需要不断的将问题分解直到返回就可以了。
总之,递归算法从思想上更加贴近人们处理问题的思路,而且所处的思想层级算是高层(神),而迭代则更加偏向于底层(人),所以从执行效率上来讲,底层(迭代)往往比高层(递归)来的高,但高层(递归)却能提供更加抽象的服务,更加的简洁。
从个人来讲,我非常认同“迭代是人,递归是神”!
**********************************随时发现,随时分享*********************************
相关文章
- Python中的可迭代Iterable和迭代器Iterator
- 当软件测试迭代测试时间不够时该如何去做好质量控制呢?
- 网络编程 -- RPC实现原理 -- RPC -- 迭代版本V4 -- 远程方法调用 整合 Spring 自动注册
- 【C++ STL应用与实现】18: 怎样使用迭代器适配器
- C#,图像二值化(14)——全局阈值的最佳迭代算法(Iterate Thresholding)及源代码
- C++程序设计:原理与实践(进阶篇)15.3 序列和迭代器
- python 递归迭代目录
- 《剑指offer》之“翻转单链表”递归、迭代、双指针解题
- Java迭代器Iterator的remove()方法
- QList类迭代器详解
- php 递归创建目录、递归删除非空目录、迭代创建目录
- 《Python参考手册(第4版•修订版)》——1.10 迭代与循环
- 4.python迭代器生成器装饰器
- C++迭代器之'反向迭代器'
- ES6 迭代器
- [js高手之路] 设计模式系列课程 - 迭代器(1)
- stylus使用文档总结:内置方法+参数+条件+迭代+导入+继承
- ES6中的迭代器(Iterator)和生成器(Generator)(一)
- 迭代器模式讲解
- 迭代器模式
- 数组迭代
- PHP设计模式——迭代模式
- 25行为型模式之迭代器模式
- 迭代器&生成器
- isinstance方法判断可迭代和迭代器
- 对JAVA集合进行遍历删除时务必要用迭代器
- 深入理解JavaScript系列(35):设计模式之迭代器模式