共计 1363 个字符，预计需要花费 4 分钟才能阅读完成。
一、递归的定义
若在一个函数、过程或者数据结构定义的内部，直接（或间接）出现定义本身的应用，则称它们是递归的，或者是递归定义的。递归函数是指一个直接调用自己或通过一系列的调用语句间接调用自己的函数。
计算机是用栈来记录每个调用中的函数。这个栈就叫作调用栈：
1、调用函数时，系统将为调用者构造一个由参数表和返回地址组成的活动记录，并将其压入到由系统提供的运行时刻栈的栈顶，然后将程序的控制权转移到被调函数。若被调函数有局部变量，则在运行时刻，在栈的栈顶也要为其分配相应的空间。因此，活动记录和这些局部变量形成了一个可供被调函数使用的活动结构。
2、被调函数执行完毕时，系统将运行时刻栈的栈顶的活动结构退栈，并根据退栈的活动结构中所保存的返回地址将程序的控制权转移给调用者继续执行。
二、递归算法的设计步骤
1、将规模较大的原问题分解为一个或多个规模更小、但具有类似于原问题特性的子问题；
2、确定一个或多个无须分解、可直接求解的最小子问题（称为递归的终止条件或基准情形）。例如，非负整数 n 的阶乘可递归定义为：
三、递归算法的优点
1、递归是一种强有力的数学工具，它可使问题的描述和求解变得简捷和清晰。
2、递归算法常常比非递归算法更容易设计，尤其是当问题本身或所涉及的数据结构是递归定义时，使用递归算法特别合适。
3、有些问题用递归算法实现既巧妙又高效。
四、递归算法的缺点
大多数情况下，它并不比普通的循环更加优雅、高效；
五、递归算法的适用场景
1、递归十分适用于那些 无法预估计算深度的问题 ，比如遍历文件系统。假设你现在要写一个脚本，它用于对一个目录下的所有文件进行某种操作（包含子目录中的文件）。
2、快排算法
详见快排算法部分。
六、递归算法的时间复杂度计算方式
1、代换法
（1）猜测解的形式
（2）用数学归纳法找出使解真正有效的常数
比如我们求解，递归式 T(n) = 2T(n/2)+n，
1- 我们猜测解是 O(nlgn), 我们要寻找到一个常数 c, 使得 T(n)<=cnlgn
2- 证明：即 T(n) <= 2c(n/2)lg(n/2)+n <= cnlgn-cnlg2+n = cnlgn-cn+n
只要 c >=1,T(n)<=cnlgn, 所以我们的猜测是正确的。
2、递归树方法
利用递归树方法求算法复杂度，其实是提供了一个好的猜测，简单而直观。在递归树中，每一个结点表示一个单一问题的代价，子问题对应某次递归函数调用。我们将树中每层中的代价求和，得到每层代价，然后将所有层的代价求和，得到所有层次的递归调用总代价。
根据上式我们建立递归式 T(n) = 3T(n / 4) + cn^2，建立下列递归树模型：
在递归树中，每一个结点都代表一个子代价，每层的代价是该层所有子代价的总和，总问题的代价就是所有层的代价总和。所以，我们利用递归树求解代价，只要知道每一层的代价和层数即可。
以上图为例，当递归调用到叶子 T(1)时所用到的递归次数就是整棵递归树的深度。我们从图中可以得到第 i 层的结点的代价为 n /(4^i)，当 n /(4^i)= 1 即 i = log4(n)时，递归到达了叶子，故整棵递归树的深度为 log4(n)。总代价是所有层代价的总和，结果为 O(n^2)。计算过程详见算法导论。
3、主方法
参考书目 ：
1、数据结构与算法：C++ 语言版 作者：肖南峰，赵洁等
2、数据结构与算法图解 作者：[美] 杰伊·温格罗
3、算法导论
