【算法】答应我，今天一定要掌握什么是函数递归！！！

函数递归

【算法】答应我，今天一定要掌握什么是函数递归！！！_C语言

导读

大家好，很高兴又和大家见面啦！！！

在上一篇内容中，我们谈论了一下我所认为的算法，以及我们学习算法应该抱有的心态。在今天的内容中，我们将开始介绍咱们需要掌握的第一个算法——递归。

递归，相信大家在学完【C语言】和【数据结构】这两个内容后，应该也是非常熟悉的。

• 在【C语言】中，我们介绍函数时就介绍了什么是递归：
• 程序调用自身的编程技巧称为递归
• 在【数据结构】中，我们在学习二叉树、快速排序、归并排序时，我们就是通过递归实现的对应的功能

如果有一直看我博客的朋友应该知道，我在C站最开始发布的几篇文章——扫雷、汉诺塔、青蛙跳台阶……其中的一些功能就是使用的递归完成的。

既然我们已经这么熟悉递归了，我们为什么还要来把这单独作为一个章节来进行说明呢？

这个问题的答案可以总结为以下几点：

• 在上一篇内容中我们就有说过，我所认为的广义的算法就是指的我们在解决问题时所编写的代码。因此算法我们就可以理解为是编程，而编程就是算法；
• 对于大部分人所说的算法，都是指的狭义的算法，如我们今天要谈论的递归，以及后面会陆续介绍的动态规划、分治……其实这些编程方法在我们之前的学习中，就已经不知不觉的融入了我们的编程中，只不过我们并不知道它的名字罢了；
• 递归作为【算法】专栏中第一个介绍的算法，是希望通过递归来帮助大家减少算法与编程的割裂感，并且减轻大家在学习算法过程中可能出现的焦虑情绪；
• 通过熟悉的递归算法，我们能够更加清晰的认识到我们将要学习的这些解决问题的编程方法离我们究竟有多近。

那接下来我们就来直接进入今天的主题——递归。

一、递归

1.1 什么是递归？

虽然大家都已经很熟悉递归了，但是为了防止有朋友还不怎么知道什么是递归，下面我们就来以一个最简单的递归来说明：

//最简单的递归
int main() {
	int ret = main();
	printf("ret = %d\n", ret);
	return 0;
}

在上例中我们编写了一个main函数，并在main函数的函数体中调用了自己，像上例程序这种自己调用自己的编程方式就是我们所说的递归。

大家可以猜一下这个程序的输出结果是什么？

【算法】答应我，今天一定要掌握什么是函数递归！！！_栈溢出_02

从输出窗口中可以看到，此时啥也没有输出，并且系统报了警告——函数运行时，堆栈溢出。

1.2 递归的本质

为了帮助大家更好的看清递归的本质，下面我们可以创建一个全局的计数变量，然后通过计数变量的值来进行观测，如下所示：

【算法】答应我，今天一定要掌握什么是函数递归！！！_算法_03

可以看到，在整个程序运行的过程中，main函数被调用了4584次，从这个输出结果我们可以得到以下信息：

• 递归就是重复的执行函数体中的代码
• 递归不能够无限制的重复，它会在运行到一定程度时终止

还没有接触过递归的朋友可能会有疑惑，这个递归怎么和循环这么像呢？它和循环又和有何联系呢？

1.3 递归与迭代

我们直接说结论——递归和迭代都是重复同一种操作的编程方式。这里的迭代就是指的循环。不过递归与迭代不同的是，递归不存在死递归，总是会有一个终止的方式，但是迭代却会出现死循环。为什么会这样呢？

有学过函数栈帧的创建与销毁的朋友应该是能够理解的，没学过的也没关系，我们今天简单的介绍一下，大家留有一个印象即可：

• 递归是不断的在栈区为函数开辟新的空间，在每一次开辟的空间中执行相同的操作；
• 迭代是在对应的开辟好的函数栈帧内执行相同的操作；
• 计算机的内存并不是无限制的，它的大小是有限的，当我们通过递归不断的向栈区申请空间时，迟早会把栈区的空间申请完，之后继续申请就会导致堆栈溢出的情况；
• 在迭代中，当我们如上例所示，只进行全局变量的自增与结果打印的话，并不会消耗额外的内存空间，因此程序不会出现内存不够的情况；

所以不管是递归还是迭代，我们都必须防止出现栈溢出与死循环的情况发生。那具体该如何做呢？

1.4 递归的必要条件

对于递归而言，它有两个非常重要且不可忽视的条件：

1. 递归需要有一个限制条件，即递归的结束条件
2. 每一次递进时都需要接近该限制条件，即递进会走向结束

这里我们还是以最简单的递归为例，我们来给该递归加上对应的限制条件，以此来避免栈溢出的情况，如下所示：

【算法】答应我，今天一定要掌握什么是函数递归！！！_栈溢出_04

可以看到，此时当我们在函数调用前加入一个结束条件后，此时的递归就能够很好的在满足条件时结束函数的继续调用。

迭代中防止死循环的措施

这里我也简单的提一下迭代中为了避免死循环的出现可以采取的措施：

1. 和递归一样，在循环中设置结束条件，并且每一次循环，都会接近该条件
2. 在循环体中设置转向语句如break、return、go to……

这里我就不再展开，我们今天重点需要关注的是递归的内容。

1.5 注意事项！！！

在递归中我们还需要注意，当我们在设置结束条件时，并不能无限制的设置，从前面的测试中我们可以看到，这里最简单的递归仅可以在内存中自我调用4584次，也就是说当我们调用了4584次main函数后，此时栈区的空间是已经被申请完了，不存在多余的空间来提供给下一次的main函数的调用。

因此在递归调用中，该结束条件的设置不能够太大，如直接设置1w、10w、100w……这些特别大的条件，也不能设置的太小，如直接设置-1w、-10w、-100w……这样的数字。因为在这种条件下，即使我们每一次的函数调用都是在接近结束条件，但是也会存在栈溢出的情况。

因此递归的调用不适合那些重复次数特别多的情况，所以当我们在处理那些结束条件特别大或者特别小的问题时，我们最好使用迭代的方式来实现。

结语

今天的内容到这里就全部结束了，在下一篇内容中我们将介绍《如何使用递归》，大家记得关注哦！如果大家喜欢博主的内容，可以点赞、收藏加评论支持一下博主，当然也可以将博主的内容转发给你身边需要的朋友。最后感谢各位朋友的支持，咱们下一篇再见！！！