请扫码加公众号
递归(recursion)算是接触的概念中于我最有吸引力的一个。
学习离散数学时，很多概念是递归定义的，感觉递归定义什么意思都没表达，但是莫名其妙就知道它会以什么形式出现，很有意思。
递归程序更有意思，程序员基本没做什么事，程序就自动完成了。
这种不劳而获的感觉
真是
太有吸引力了。
递归到底是个什么鬼？
在回答这个问题前，先看一下递归的原型（数学内的，不过放心，没有积分之类的鬼东西）
数学上的递归
递归这个东西在高中数学就有出现，典型的是斐波那契数列：
F（n）=F(n-1)+F(n-2)
如果给定了初始的F（0）和F（1），这样整个数列的值也都是知道了。
斐波那契数列在手工求值的时候会比较麻烦，我们通过等比数列来描述递归是怎样运作的。（数学上）
A(n)=A(n-1)*2，A（0）=1
如果我们要求A（100），那么我们就要求A（99）
求A(99)就要求A(98)
求A(98)就要求A(97)
如此重复下去，我们为求A（1）的到A（0），因为A（0）已知，乘2即可的A（1）
这一部分叫分解
然后在用A(1)求A(2)…..用A(2)求A(3)
最后求得A(99),
然后由A（99）得到A（100）
这一部分叫啥我不知道，资料里面都是说合并，结合一类的，我喜欢用返回（因为的确是慢慢往最初的调用A(100)返回了）
数学上的递归有如下特征：
有基本情况
如等比数列的A(0),斐波那契F(0),F(1)
所有的复杂情况都可以转换成基本情况。
如果转换不成，这就不是一个成功的递归，因为你必须的想出一个其他方式来解决问题
复杂情况转化到简单一级情况的是一个函数关系（也就是说最后的复杂情况下是单值的，不可能出现重值情况）
计算机里的递归
递归也就是一个function调用自身。比如说
voidaFun(int n)
{
statement;
aFun(n-1);
}
不过，这只是递归的形式而已，或者说函数调用自身只是递归的一个特点，递归的内涵要比自身调用自身这句简单的话深刻许多。
与递归最接近的思想叫做分治法（divide-and-conquer），当然递归还与别的相关，分治法是一个特别能直接体现递归解决问题的思路的方法。（递归回归到数学上本质是归纳法）
分治法描述：将原问题分解为几个规模较小的类似原问题的子问题，然后用同样的方式递归解决这些问题，最后在合并这些子问题的解来建立原问题的解。
这一种描述很精巧，其中有几个关键的细节。
第一：分解的子问题能够采取同样的方式解决
第二：必须要有递归底层
第三：必须要有一个合并算法
第一点是很明显的，也是递归最容易让人记住的。子问题和大问题能够同样解决，但是说实话，这不是递归的难点。
在真正编写的时候，往往只是根据函数原型改写一个参数。唯一可能有点难度的就是说有时候要想办法构造一种变换把大问题转换成同样的小问题。
第二点．递归底层指的是最小的基本情况，就如斐波那契数列中的F（0）,F（1）。如果没有这个递归底层，程序在运行的时候就会不断得改变参数，不断得调用自身，比如参数的变化规律是减去1，那么函数就会从function(100)一直递归到function(-300)…….直到内存因为函数帧爆掉。这和数学上是一样的，没有这个基本情况，计算机根本不可能完成任务。
第三点，合并算法。在真正编写递归函数的时候这是实现的灵魂。
只要脑子清醒，参数写的正确，计算机总能调用到递归的底层进行一些很细小的处理，那么说到了递归底层以后呢？发散出了那么多，最开始的问题还是没有解决吧。
这时候就要有用到合并算法往回解决了，通过合并算法往最初情况走。
什么意思？既然已经达到了递归的最基本情况，并且解决了最基本情况，那么接下来的事情就是综合这些结果。
比如我们最后递归下来有64个基本情况，合并算法是两两合并解决的，这样问题规模就变成32，继续合并变成16，最后回到1的情况。
