Java学习平台

先来解释一下函数的调用过程。

序号	函数调用层级
5	done()
4	something()
3	good()
2	begin()
1	function()
0	main()

这个表格是一个假设的函数调用关系，表格最下面那行，是main函数，然后main函数调用了function，等待function完成，main函数才能继续；同理，function等待begin函数，以此类推。
这样的结构，叫做栈，它最明显的特征就是：后进先出。
例如表格里面，最后调用done函数，最早结束，然后是something函数，以此类推，最后一个结束的函数，是最早运行的main函数。
你也可以把栈想象成一筒薯片，最早放下去的薯片，最后才被吃掉。
而这些函数之间的调用，可以是同一个函数，这就是递归。

5	fun(0)
4	fun(1)
3	fun(2)
2	fun(3)
1	fun(4)
0	fun(5)

而fun(0)的时候，函数不再递归，而是返回了值，然后fun(1)返回了值，以此类推。
递归是一种比较特殊的函数调用，用来解决一些这样的问题：问题可以分成更简单的两个问题，而这两个问题和原问题是同源的。
例如排序sort，可以分解成
1.数组前半部分排序，数组后半部分排序
2.合并两个数组，最后整个数组排序
这个算法叫做归并排序，它是一种比选择排序、冒泡排序效率更高的排序，样本越大，差距越大。
我们可以把这个算法叫做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，简化到最后有结束的条件。例如斐波那契数列的计算，也可以用递归计算

调用的展开，其实是一棵“树”。例如fibonaqi(5)

fibonaqi(5)的计算，变成了fibonaqi(4)和fibonaqi(3)的计算，fibonaqi(4)又变成fibonaqi(3)和fibonaqi(2)的计算，fibonaqi(3)变成fibonaqi(2)和fibonaqi(1)的计算，fibonaqi(2)和fibonaqi(1)这两个是直接可以算出结果无需递归。