5.11 *递归

先来解释一下函数的调用过程。
序号
函数调用层级
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)返回了值，以此类推。
递归是一种比较特殊的函数调用，用来解决一些这样的问题：问题可以分成更简单的一个或多个问题，而这个（些）问题和原问题是同源的。
递归总结起来两点：
1.能把x规模的问题简化成一个或者多个x-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)这两个是直接可以算出结果无需递归。
然后fibonaqi(3)就可以算出来了，以此往上最终计算出fibonaqi(5)。
下面是计算指定位置的斐波那契数的一个递归实现：
def fibonaqi(x):
    if x==1 or x==2:
        return 1
    return fibonaqi(x-1)+fibonaqi(x-2)
print(fibonaqi(5))

有一种排序算法叫做归并排序，可以分解成：
1.归并排序前半部分，归并排序后半部分；
2.合并两部分，最后整体排序。
光看这个，会有一种好像什么也没做的感觉。然而只要这个前半或者后半的列表仅仅只有一个元素，那么它就是排好序的，而一个列表只要细分下去一定会分到仅仅只有一个元素的情形。

归并排序是一种比选择排序、冒泡排序效率更高的排序，样本越大，差距越大。列表前半部分的排序又用到归并排序，前半部分的前半部分再次用到归并排序。
递归非常容易造成死循环，所以必须有函数完成的条件。例如列表长度是1的时候，排序完成。 
1.如果列表长度等于1，已经排好序直接返回，否则把列表按中间分成两个列表list1和list2
2.用归并排序给列表list1排序
3.用归并排序给列表list2排序
4.合并两个排好序的列表，最终整个列表排好序。

我们用一个列表来试试这个算法 arr =[23 , 14 , 56 , 1 , 35 , 89 , 99 , 65 , 73 , 44]
下面开始递归，高能预警：
1.列表长度大于1，分成两个列表[23 , 14 , 56 , 1 , 35]和[89 , 99 , 65 , 73 , 44]
2.用归并排序给列表[23 , 14 , 56 , 1 , 35]排序
  2.1 列表长度大于1，分成两个列表[23,14]和[56,1,35]
  2.2 用归并排序给列表[23,14]排序
    2.2.1列表长度大于1，分成两个列表[23]和[14]
    2.2.2用归并排序给列表[23]排序
      2.2.2.1 列表长度等于1，已经排好序直接返回
    2.2.3用归并排序给列表[14]排序
      2.2.3.1 列表长度等于1，已经排好序直接返回
    2.2.4 合并两个排好序的列表[14,23]
  2.3 用归并排序给列表[56,1,35]排序
    2.3.1 列表长度大于1，分成两个列表[56]和[1,35]
    2.3.2 用归并排序给列表[56]排序
      2.3.2.1 列表长度等于1，已经排好序直接返回
    2.3.3 用归并排序给列表[1,35]排序
      2.3.3.1 列表长度大于1，分成两个列表[1]和[35]
      2.3.3.2 用归并排序给列表[1]排序
        2.3.3.2.1 列表长度等于1，已经排好序直接返回
      2.3.3.3 用归并排序给列表[35]排序
        2.3.3.3.1 列表长度等于1，已经排好序直接返回
      2.3.3.4 合并两个排好序的列表[1,35]
    2.3.4 合并两个排好序的列表[1,35,56]
  2.4 合并两个排好序的列表[1,14,23,35,56]
3.用归并排序给列表[89 , 99 , 65 , 73 , 44]排序
...省略
4.合并两个排好序的列表