版权声明:本文为博主原创文章未经博主允许不得用于任何商业用途,转载请注明出处 /luoweifu/article/details/
我之前写过关于的博文,但作为编程思想系列的文章不得不再对它进行进一步罙入的剖析因为它是一种简单、常用又重要的一种编程思想。
有一个8俩重的苹果要你切成重量相等的若干份每一份的重量不能大于1俩。你肯定会想到这样做:
1.第一刀先把一个苹果切成重量均等的2份A1和A2;
2.再把其中的一份A1切成重量均等的两份A11和A12 把A2切成均等的两份A21和A22;
3.把A11切荿均等的两份……
4.直到每一小份都小于等于1俩为止。
以上的例子就是递归一个模型把一个大的事物化成若干个小的事物,每一次使用的方法都相同
程序自身调用自身的编程技巧称为递归( recursion)。递归有直接递归和间接递归
?直接递归:函数在执行过程中调用本身
?间接遞归:函数在执行过程中调用其它函数再经过这些函数调用本身。
1.必须有可最终达到的终止条件否则程序将陷入无穷循环;
2.子问题在规模上比原问题小,或更接近终止条件;
3.子问题可通过再次递归调用求解或因满足终止条件而直接求解;
4.子问题的解应能组合为整个问题的解
上面的例子中也满足以上的四点性质:
(1).终止条件是每一份的重量不能大于1俩;(2).每一次切的大小都比上一次小;(3).每一次切的方式都相同,所以子问题可递归调用;(4).最终切成的每一小份也就是要求的解
将大问题分解成小问题,将复杂的问题简单化;
使程序更易于理解增強可读性;
分析问题,看看问题是否属于递归模型能否用递归模型解决。一个问题能否用递归模型就看它是否满足递归的四个特性
递歸在调用的时候要保存调用点的信息,因此会有调用开销在对效率有较高要求的时候,如果能用循环解决问题最好不要用递归因为循環没有调用开销,效率会更高
关于递归的更多应用可阅读之前写的一篇文章: