认识递归(详细版).docx

认识递归

递归是程序设计和算法学习中经常遇到的一类问题，递归解题本身也是很多比

赛中常用的一种解题方法，那么什么是递归呢，我们不妨从下面的小视频开始

我们的递归之旅。

https://www.zhihu.com/zvideo/1223322961979039744

相信通过上面的小动画，同学们应该对递归有了一个初步的了解了，等你学完

本节课再回头看看这个小动画，我相信你对递归肯定有一个更深入的理解。那

么究竟什么是递归，递归又能干什么呢？

if (n < =1)

return 1;

return n * factorial(n - 1);

}

Copy

进一步解释递归问题。“递”的意思是将问题拆解成子问题来解决， 子问题再拆

解成子子问题，.....，直到被拆解的子问题无需再拆分成更细的子问题（即可以

求解），“归”是说最小的子问题解决了，那么它的上一层子问题也就解决了，

上一层的子问题解决了，上上层问题自然也就解决了,....,直到最开始的问题解

决,文字说可能有点抽象，那我们就以阶层 f(6) 为例来看下它的“递”和“归”。

递归算法解题思路

根据以上分析，不难发现递归问题有以下特点：

一个问题可分解成具有相同解决思路的子问题、子子问题，即这些问题都可调

用同一个函数。

经过层层分解的子问题最后一定有一个不能再分解的固定值（即终止条件）,如

果没有的话就无穷无尽地分解子问题，问题显然是无解的。

解递归题的关键在于我们首先需要根据以上特点判断题目是否可以用递归来解。

经判断可以用递归后，接下来看看用递归解题的基本套路：

递归解题的基本套路

（1）先定义一个函数，明确这个函数的功能，由于递归的特点是问题和子问

题都会调用函数自身，所以这个函数的功能一旦确定了， 之后只要找寻问题与

成子问题时，子问题可以调用步骤 1 定义的函数，符合递归的条件（函数里调

用自身）。

（3）将第二步的递推公式用代码表示出来补充到步骤 1 定义的函数中。

（4）最后也是很关键的一步，根据问题与子问题的关系，推导出时间复杂度,

如果发现递归时间复杂度不可接受，则需转换思路对其进行改造，看下是否有

更靠谱的解法。

实例说明