一：什么是递归

递归，简单来说就是函数直接或间接调用自身的方法，通常是将大的复杂问题转换为与原问题相似的小规模问题来求解。

我们可以把“递归”比喻成“查词典”。 yydcdq查了词，发现这句话说明里的词还不明白，于是你开始查这第二个词。

很遗憾，第二个词还有不明白的词。 因此，我们要调查第三个词。 这样，一直调查到完全明白一个词的说明为止。 那么，递归地走到尽头。 然后，开始后退，一个接一个地理解之前调查过的所有词语。 最终，我们会明白第一句话的意思。 (摘自知道的回答() ) () ) ) ) ) )。

我们把阶乘

国际工业(国际) {

if(n==0)返回1；

返回

n *工厂(n-1 )；

}

二：递归与栈的关系

经常听到“递归的过程是进出栈的过程”这个词，这个词怎么理解？ 以上述代码为例，如果n=3，则进程如下。

步骤1~4都是堆栈过程，factorial(3)调用factorial ) 2，factorial )2)调用到factorial )0)为止

步骤5、0是递归结束条件，因此不再进入堆栈。 在这种情况下，堆栈的高度为4，是我们平时所说的递归深度；

步骤6~9中，factorial(0)完成，退出堆栈。 另外，factorial )0)完成也就是说，factorial )1)也完成了，同样地推出堆栈，反复进行直到全部离开堆栈，然后递归地结束。

每个递归程序都可以将其重写为非递归版本。 只需利用堆栈，即可通过堆栈和出栈两种操作模拟递归过程。 二叉树遍历无疑是其中的代表。

但是，并不是所有的递归程序都那么容易被非递归改写。 有些递归程序很复杂，其入站和出站非常复杂，给编码带来很大困难，而且可读性极差，所以建议在条件允许的情况下递归。

第一次学习

三：如何思考递归

递归时，看到递归的实现，我们总是不可避免地陷入验证。 例如，在求解上述阶乘，factorial(n )时，我们会情不自禁地提问。 factorial(n-1 )能求出正确的答案吗？ 然后，继续验证到factorial (用0 (n-2 )验证，factorial )0)。

递归这个不适应关系到我们平时习惯和亲近的想法。 我们习惯的思维是，知道factorial(0)，乘以1就是factorial ) 1，乘以2就是factorial ) 2，直到乘上、n。

递归和我们的想法正好相反。

那么，如何判断这个递归计算是否正确呢？ Paul Graham谈到了以下方法。

如果以下两点成立，你就会发现这个递归对所有n都是正确的。

n=0，1时，结果是正确的；

假设递归对n是正确的，同时对n 1也是正确的。

这个方法类似于数学归纳法，也是递归正确的想法。 上述第一点称为基本情况，第二点称为共同情况。

递归中，通常把第一点称为终止条件。 因为那样更容易理解。 其作用是中止递归，防止递归无限期地执行下去。

让我用两个例子具体说明这个数学归纳法：

例1汉诺威展开目录

提问说明有三根棍子a、b、c。 a杆有n个穿孔圆盘，盘的尺寸从上到下依次变大，b、c杆为空。 要将所有磁盘移动到c杆，请遵循以下规则：

一次只能移动一个圆盘；

大盘子不能叠在小碟上。

问：怎么移动？ 最少移动几次？

首先，在基本情况下，即结束条件： N=1时，从a直接转移到c。

让我们再来看看一般情况。 当a上面有n个圆盘的时候，我们找到了把它移动到c杆上的方法。 怎么把N 1个圆盘移动到c棒上？ 很简单。 首先，用将n个圆盘移动到c的方法，将n个圆盘全部移动到b，然后将第N 1个圆盘(最后的圆盘)移动到c，用同样的方法将b条上的n个圆盘移动到c，从而解决问题。

代码如下所示。

void Hanoi (英寸、字符a、字符b、字符c )//结束条件

if(n==1) )。

{

出口端；

返回；

() /共同情况

Hanoi(n-1、a、c、b )；

Hanoi(1 (一、甲、乙、丙)；

Hanoi(n-1、b、a和c )；

}

例2求出二叉树的节点数，展开目录

我们先来看看基本情况，即终止条件。 对于空树，节点数为0。

如果求出当前节点的左、右部分树的节点数，则以当前节点为根的二叉树的节点总数为“左部分树右部分树1”。

代码如下所示。

intgetnodes (节点*节点) )//结束条件

if (节点==空值) )。

返回0； //共同情况

返回

节点(左节点)节点(右节点) 1；

}

四：什么时候该用递归

发生问题时，我们是如何判断那个问题得到了递归解决的

要递归解决问题，需要以下条件：

子问题和原问题是一回事，必须规模更小

程序停止条件。

递归学习绝对是持久战，没有人能一蹴而就。 一年两年的，很普通。