To iterate is human,to recurse divine. ---L.Peter Deutsch

这句经典名言体现了递归算法的重要性，虽然执行效率不如迭代法，但它可以使那些很复杂的问题化成简单化。

递归

一、递归概念

二、程序示例

1、划一刀思维（切蛋糕思维）

（1）n的阶乘

问题描述：求5的阶乘

图解理解

代码

（2）打印i——j的值

代码

（3）对array的所有元素求和

代码

（4）字符串翻转

代码

小结

2、多规模的子问题

（1）斐波拉契

问题描述

代码

（2）最大公约数

问题描述

代码

小结

三、总结

一、递归概念

递归，在数学与计算机科学中，是指在方法的定义中使用方法自身。也就是说，递归算法是一种直接或者间接调用自身方法的算法。简言之：在定义自身的同时又出现自身的直接或间接调用。

注意：递归必须要有一个退出的条件!

递归算法解决问题的特点： 1）递归就是方法里调用自身。 2）在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。 3）递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。 4）在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等，所以一般不提倡用递归算法设计程序。

在做递归算法的时候，一定要把握住出口，也就是做递归算法必须要有一个明确的递归结束条件。这一点是非常重要的。

其实这个出口是非常好理解的，就是一个条件，当满足了这个条件的时候我们就不再递归了。

二、程序示例

1、划一刀思维（切蛋糕思维）

（1）n的阶乘

问题描述：求5的阶乘

图解理解

代码

public class Demo6 {

public static void main(String[] args) {

System.out.println(fact(5));

}

/**

* 求n的阶乘f1（n) 求n的阶乘--->fact（n-1）求n-1的阶乘

* 1.找重复(规模更小）；n*(n-1)的阶乘，求n-1的阶乘是原问题的重复（规模更小）——子问题

* 2.找变化；变化的量应作为参数

* 3.找边界；出口

*/

public static int fact(int n) {

if(n == 1) {

return n = 1;

}else {

return n*fact(n-1);

}

}

}

运行结果：

（2）打印i——j的值

代码

public class Demo6 {

public static void main(String[