7.10 *递归
先来解释一下函数的调用过程。
| 序号 | 函数调用层级 |
|---|---|
| 5 | done() |
| 4 | something() |
| 3 | good() |
| 2 | begin() |
| 1 | function() |
| 0 | main() |
这个表格是一个假设的函数调用关系，表格最下面那行，是main函数，然后main函数调用了function，等待function完成，main函数才能继续；同理，function等待begin函数，以此类推。
这样的结构，叫做栈，它最明显的特征就是：后进先出。
例如表格里面，最后调用done函数，最早结束，然后是something函数，以此类推，最后一个结束的函数，是最早运行的main函数。
你也可以把栈想象成一筒薯片，最早放下去的薯片，最后才被吃掉。
而这些函数之间的调用，可以是同一个函数，这就是递归。
| 序号 | 函数调用层级 |
|---|---|
| 4 | fun(0) |
| 3 | fun(1) |
| 2 | fun(2) |
| 1 | fun(3) |
| 0 | fun(4) |
而fun(0)的时候，函数不再递归，而是返回了值，然后fun(1)返回了值，以此类推。
递归是一种比较特殊的函数调用，用来解决一些这样的问题：问题可以分成更简单的一个或多个问题，而这个（些）问题和原问题是同源的。
例如排序sort，可以分解成
1.数组前半部分排序，数组后半部分排序 ；
2.合并两个数组，最后整个数组排序。
这个算法叫做归并排序，它是一种比选择排序、冒泡排序效率更高的排序，样本越大，差距越大。
我们可以把这个算法叫做A，然后数组前半部分的排序又用到A算法，前半部分的前半部分再次用到A算法。
递归非常容易造成死循环，所以必须有函数完成的条件。例如数组长度是1的时候，排序完成。
我们用一个数组来试试这个算法A
int arr[] ={23 , 14 , 56 , 1 , 35 , 89 , 99 , 65 , 73 , 44};
1.用算法A给数组{23 , 14 , 56 , 1 , 35}排序
2.用算法A给数组{89 , 99 , 65 , 73 , 44}排序
3.合并两个排好序的数组，最终整个数组排好序。
下面开始递归，高能预警：
1.1 用算法A给数组{23 , 14 }排序
1.2用算法A给数组{56 , 1 , 35}排序
1.3合并两个排好序的数组
其中
1.1再次递归
1.1.1用算法A给数组{23}排序
1.1.2用算法A给数组{14}排序
1.1.3合并两个排好序的数组
这次不用递归了，
1.1.3返回了{14,23},也就是1.1结束了
1.1用算法A给数组{23 , 14 }排序，执行完变成{14,23}
1.2用算法A给数组{56 , 1 , 35}排序，执行中...
1.2开始递归
1.2.1用算法A给数组{56}排序
1.2.2用算法A给数组{1 , 35}排序
递归...
1.2.2.1用算法A给数组{1}排序
1.2.2.2用算法A给数组{35}排序
1.2.2.3合并两个排好序的数组{1 , 35}
...
递归下去还有很长。
递归总结起来两点：
1.能把问题简化，
2简化到最后有结束的条件。
例如斐波那契数列的计算，也可以用递归计算
public static int fibonaqi(int x){
if(x==1 || x==2)
return 1;
return fibonaqi(x-1)+fibonaqi(x-2);
}
调用的展开，其实是一棵“树”。例如fibonaqi(5)
fibonaqi(5)的计算，变成了fibonaqi(4)和fibonaqi(3)的计算；
fibonaqi(4)又变成fibonaqi(3)和fibonaqi(2)的计算；
fibonaqi(3)变成fibonaqi(2)和fibonaqi(1)的计算；
fibonaqi(2)和fibonaqi(1)这两个是直接可以算出结果无需递归。
然后fibonaqi(3)就可以算出来了，以此往上最终计算出fibonaqi(5)。
