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[] args) {

fact(1,10);

}

/**

* 打印i——j的值

* 1.找重复(规模更小）；i越来越靠近j——子问题

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

* 3.找边界；出口

*/

public static void fact(int i, int j) {

if(i > j) {

return ;

}else {

System.out.println(i);

fact(i+1, j)

}

}

}

运行结果：

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

代码

public class Demo6 {

public static void main(String[] args) {

System.out.println(fact(new int[] {1,5,8,10,55}, 0));

}

/**

* 对array的所有元素求和

* 1.找重复(规模更小）；开始begin一直变化——子问题

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

* 3.找边界；出口

*/

public static int fact(int array[], int begin) {

if(begin == array.length-1) {

return array[begin];

}else {

return array[begin] + fact(array,begin + 1);

}

}

}

运行结果：

（4）字符串翻转

代码

public class Demo6 {

public static void main(String[] args) {

System.out.println(reverse("abcdef", 5));

}

/**

* 字符串翻转

* 1.找重复(规模更小）；开始end一直变化——子问题

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

* 3.找边界；出口

*/

public static String reverse(String src, int end) {

if(end == 0) {

return "" + src.charAt(end);//charAt是按照索引获得字符串的指定字符

}else {

return src.charAt(end) + reverse(src, end - 1);

}

}

}

运行结果：

小结

分解为：直接量 + 小规模子问题

2、多规模的子问题

（1）斐波拉契

问题描述

1,1,2,3,5,8… 递推公式f(n) = f(n-1) + f(n-2)

代码

public class Demo6 {

public static void main(String[] args) {

System.out.println(fib(10));

}

/**

* 斐波拉契：1,1,2,3,5,8... 递推公式f(n) = f(n-1) + f(n-2)

* 1.找重复(规模更小）；n一直变化——子问题

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

* 3.找边界；出口

*/

public static int fib(int n) {

if(n == 1 || n == 2) {

return 1;

}else {

return fib(n-1) + fib(n-2);

}

}

}

运行结果：

（2）最大公约数

问题描述

最大公约数 f(m,n) = f(n,m%n)

代码

public class Demo6 {

public static void main(String[] args) {

System.out.println(f4(10,3));

}

/**

* 最大公约数 f(m,n) = f(n,m%n)

* 1.找重复(规模更小）；n一直变化——子问题

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

* 3.找边界；出口

*/

public static int f4(int m, int n) {

if(n == 0) {

return m;

}else {

return f4(n,m%n);

}

}

}

运行结果：

小结

分解多规模的子问题：划不开，有没有递推公式？有没有等价转换？

三、总结

找重复： 1.找到一种划分的方法 2.找到递推公式或者等价转换 这些都是父问题转化为求解子问题找变化的量：变化的通常要作为参数找出口

（ps：平时做题什么之类的，能用循环都不要用递归算法）