深入理解递归（一）

内容会持续更新，有错误的地方欢迎指正，谢谢!

什么是迭代和递归

迭代的是人，递归的是神。 –L. Peter Deutsch

简单的定义: 当函数直接或者间接调用自己时，则发生了递归。但递归并不直观, 也不符合我们的思维习惯。因为递归的过程就是出入栈的过程。所以，每个递归程序都可把它改写为非递归版本，只需利用栈，通过入栈和出栈两个操作就可以模拟递归的过程，比如：二叉树的遍历。

如何思考递归

例子：
n的阶乘

int func(int n)
{
    if(n<=1)
    {
        return 1;
    }
    return n*func(--n);
}

我们习惯的思维是：已知Factorial(0)，乘上 1 就等于Factorial(1)，再乘以 2 就等于Factorial(2)，，，直到乘到 n。而递归和我们的思维方式正好相反。那我们怎么判断这个递归计算是否是正确的呢？

Paul Graham提到一种方法， 算是递归正确的思考方式，该方法如下：
1. 当n=0, 1的时候，结果正确。
2. 假设函数对于n是正确的，函数对n+1结果也正确。
如果这两点是成立的，我们知道这个函数对于所有可能的n都是正确的。

其实就是数学归纳法，第 1 点称为基本情况，第 2 点称为通用情况。最重要的是第1点，如果我们去掉if(n<=1)这个基本情况后, 代码会进入死循环，永远不会结束，所以，把第 1 点称为终止条件。

递归的实现

递归的模板：

void f()  
{  
     if(符合边界条件)  
    {  
       ///////  
        return;  
    }  

     //某种形式的自调用  
     f();  
}  

既然递归比迭代更难理解，为啥我们还要用递归呢？因为有些问题用递归来解决要省时省力很多！
例子：斐波拉契数列：f(0)=0 f(1)=1 f(n)=f(n-1)+f(n-2)
迭代实现：

int Fibo(int n)
{
    int f2=0 , f0=0 , f1=1;
    for(int i=0;i<n-1;++i)
    {
        f2=f0+f1;
        f0=f1;
        f1=f2;
    }
    return f2;
}

递归实现：

int Fibo(int n)
{
    if(n==0)
        return 0;
    if(n==1)
        return 1;
    return Fibo(n-1)+Fibo(n-2);
}

递归来实现，再简单不过了（但此题用递归，时间复杂度很高）

有上面的例子可得，有递归算法描述后，程序很容易写，那么关键问题就是怎么得到递归算法描述？
Paul Graham方法，只需要做两件事情：

1. 如何通过有限的步骤, 来解决最小的问题（基本用例）。
2. 如何解决问题的一般情况, 通过将问题切分成有限小并更小的子问题。

如果这两件事完成了, 那问题就解决了。这个过程还是数学归纳法的思想。

Paul Graham方法实现递归

1.汉诺塔问题：

基本情况：
当有1个圆盘在A上, 我们直接把圆盘移动到C上即可。

通用情况：
当有N个圆盘在A杠上，我们已经找到办法将其移到C杠上了，我们怎么移动N+1个圆盘到C杠上呢？很简单，我们首先用将N个圆盘移动到C杠上的方法将N个圆盘都移动到B杠上，然后再把第N+1个圆盘(最后一个)移动到C杠上，再用同样的方法将在B杠上的N个圆盘移动到C杠上。问题解决。

算法描述大概就是上面这样，其实也可以看作思维的过程。
A为存放盘子的塔，B为辅助塔，C为目标塔。
算法分为三步：
一、将A上n-1个盘子全部放到B塔上
二、将A上剩下的一个盘子放到C塔上
三、将B塔上的n-1个盘子全部放到C塔上
注：不需要考虑如何移动n-1个盘子，考虑得越多，越谜，还是把人生活得快乐些吧~

void HanoTower(int n,char from,char temp,char to)
{
    if(n==1)
        cout<<"From "<<from<<" To "<<to<<endl;
    else
    {
        HanoTower(n-1,from,to,temp);
        HanoTower(1,from,temp,to);
        HanoTower(n-1,temp,from,to);
    }
}
int main()
{
    HanoTower(3,'A','B','C');
    return 0;
}

当n=3时的输出：
From A To C
From A To B
From C To B
From A To C
From B To A
From B To C
From A To C

看起来这么复杂的问题，用递归这么容易，没有想到吧。要是用迭代来解决这个问题呢？你试试吧，试完就能体会到递归的好处了。

求二叉树结点个数

基本情况（即终止条件）：若为空树，返回0
通用情况：假设当前结点的左右子树的结点个数都已被求出，那以当前结点为根结点的树的结点个数为：左子树的结点个数+右子树的结点个数+1

什么时候用递归

问题可用递归来解决需具备的条件：

1. 子问题需与原问题为同样的事，且规模更小；
2. 有程序停止条件。

要搞定递归，只有一个方法：敲代码。
去哪敲？

1. 二叉树的各种面试笔试题目
2. DFS的题目，LeetCode上一大堆。

做了30题，就能理解递归了。

写递归函数的注意项（了解）

除了强烈建议使用Paul Graham方法以外，还有几点需要注意：

1. 要分析不满足条件时的处理方式：
就是正确的情景考虑到了后还要考虑错误的情景。
2. 要分析清楚满足递归的条件，并全部列出：
写之前就一定要想清楚什么时候这个函数会调用自己，为了防止疏漏条件，最好把所有满足递归的条件都列在纸上或者文档上。
3. 要分析递归函数的返回值：
如果递归函数有返回值，那么每执行完一次递归函数后，如何接收、处理该递归函数的返回值。
4. 写完递归函数后一定要进行单元测试：
可将递归的次数和递归后的结果打印出来，看看打印后的结果是否符合自己的预期。测试的时候一定要涉及到所有满足递归的条件，每一条件分支都要检查一遍。

递归总结（了解）

优点：结构清晰，可读性强，为设计算法、调试程序带来很大方便。
缺点：在递归调用中，系统为每一层的返回点、局部量等开辟了栈来存储，易造成栈溢出。

递归算法一般用于解决三类问题：
1. 数据的定义是按递归定义的（也就是有递推式）。(Fibonacci函数)
2. 问题解法按递归算法实现。(汉诺塔问题)
3. 数据的结构形式是按递归定义的。(树的遍历，图的搜索)

递归算法可以分为三种类型：基于递归策略的分治算法、基于递归策略的自顶向下的动态规划算法、基于递归策略的回溯算法。

a.基于递归策略的分治法（先拆，再解，后合），当问题能分解为独立的子问题，就可以使用分治法。
举例：
1. 阶乘
2. 斐波拉契数列（又叫 爬楼梯问题）
3. 汉诺塔问题
4. 矩阵乘法Strassen’s算法
5. 最近点对问题

b.基于递归策略的动态规划（自顶向下类型）：
当问题不能分解为独立的子问题，却又符合最优化原理时，就可以使用动态规划法。
举例：
1. 装配线排程问题
2. 最长共同子序列问题
3. 背包问题

c.基于递归策略的回溯：
当问题找不到数据间的相互关系、也不能将问题分解为独立的子问题，就只有把全部解都列出来，才能推断出问题的解。遍历问题各个可能解的通路，当发现此路不通时，回溯到上一步继续尝试别的通路。
1.DFS（深度优先搜索）

参考

【1】写递归函数的正确思维方法
http://blog.csdn.net/vagrxie/article/details/8470798
【2】如何编写递归程序（分治法）
http://blog.csdn.net/xgf415/article/details/52026961
【3】算法策略的总结
http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741482.html