文档介绍：递归
一 基本知识
<1> 递归中每次循环都必要使问题规模有所缩小。
<2> 递归操作每两步都是有紧密联系，如在“递归”“归操作时”，前一次输出就是后一次输入。
<3> 当子问题规模足够小时，必要可以直接求出该规模问题解，其实也就是必要要有结束递归条件。
二 递归要解决什么问题呢?
1 不同办法体之间传递
public static void main(String[] args) {
g();
}
private static void g() {
f(3);
}
private static int f(int i) {
return i+k(i);
}
private static int k(int i) {
return i;
}
2 相似办法体 不同办法名之间传递
public static void main(String[] args) {
int i = g(4);
(i);
}
private static int g(int i) {
return i*g1(3);
}
private static int g1(int i) {
return i+g2(2);
}
private static int g2(int i) {
return i*g3(1);
}
private static int g3(int i) {
return i;
}
3 看一看得出 其实功能相似因此直接使用递归
public static void main(String[] args) {
int i = g(4);
(i);
}
private static int g(int i) {
if(i == 1){
return i;
}
return i*g(i-1);
}
依照 2 与 3 比较明显看得出 使用递归明显缩短了代码使用量
4 递归使用框架
返回值类型 f(形参){
if(终结条件){
return 成果;
}
else{
return f(形参递减或者递增);
}
}
5递归算法普通用于解决三类问题：
(1)数据定义是按递归定义。（Fibonacci函数）
(2)问题解法按递归算法实现。
此类问题虽则自身没有明显递归构造，
但用递归求解比迭代求解更简朴，如汉诺塔
(3)数据构造形式是按递归定义。
如二叉树、广义表等，
由于构造自身固有递归特性，则它们操作可递归地描述。
三 典型 案例
1 斐波纳契数列
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”，指是这样一种数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归办法定义：F（0）=0，F（1）=1，F（n）=F(n-1)+F(n-2)（n≥2，n∈N*）
public static int f(int x){
if(x == 0){
return 0;
}
if(x == 1 || x == 2){
return 1;
}
return f(x-1)+f(x-2);
}
2 阶乘
public static int f(int x){
if(x == 1){
return 1;
}else{
return x*f(x-1);
}
}
3全排列
4汉诺塔
public static void hanoi(int n，char origin，char assist，char destination) {
if (n == 1) {
("Direction:" + origin + "--->" + destination);
} else {
hanoi(n - 1，origin，destination，assist);
("Direction:" + origin + "--->" + destination);
hano