递归算法

1. 前言

本节内容是递归算法系列之一：递归的介绍，主要介绍了递归的定义，选择了数学归纳法这一数学模型帮助大家可以更好的理解递归的概念，然后明确了一个递归算法必须要具备的三要素，最后说明了一下哪些问题适合应用递归算法求解分析。

2. 什么是递归？

递归（Recursion），是计算机科学与技术领域中一种常见的算法思想。

在数学和计算机领域中，递归主要是指在函数的定义中使用函数自身的方法。顾名思义，递归主要包含两个意思，递和归，这个是递归思想的精华所在。递归就是有去（递去）有回（归来）。“有去” 是指递归问题可以分解成若干个规模较小、与原问题形式相同的子问题，这些子问题可以和原问题用相同的方法来求解。“有回” 是指这些问题的演化过程是一个从大到小，并且最终会有一个明确的终点，一旦达到终点，就可以从终点原路返回，解决原问题。

更为直接的说法就是：递归的基本思想就是把大问题转化为相似的小问题解决。特别是在程序中的函数实现时，大问题的解决方案和小问题是一模一样的，所以就产生解决一个问题会调用函数本身的情况，这个也是递归的定义。

3. 用数学归纳法理解递归思想

很多时候，大家都在思考递归在数学上面应该如何表示了，毕竟对于数学的简单理解比起我们直接写代码起来还是要简单很多的。观察递归，我们会很容易发现递归的数学模型类似于数学归纳法，这个在高中的数列里面就已经开始应用了。数学归纳法常见的描述如下

最简单和常见的数学归纳法是证明当 n 等于任意一个自然数时某命题成立。证明分下面两步：

1. 证明当 n= 1 时命题成立。
2. 假设 n=m 时命题成立，那么可以 推导出在 n=m+1 时命题也成立。（m 代表任意自然数）

数学归纳法适用于将需要解决的原问题转换为解决他的子问题，而其中的子问题又可以变成子问题的子问题，而且这些问题都是同一个模型，可以用相同的处理逻辑归纳处理。当然有一个是例外的，就是归纳结束的那一个处理方法不能适用于其他的归纳处理项。递归同样的是将大的问题分解成小问题处理，然后会有一个递归的终止条件，满足终止条件之后开始回归。

数学里面有一个很有名的斐波那契数列，我们在编程求解斐波那契数列的时候就会用到递归的思想，在后续的内部中会具体讲到。

4. 递归的三要素

在明确递归的定义及数学模型之后，我们需要掌握递归的三要素：

1. 递归终止条件；
2. 递归终止时候的处理方法；
3. 递归中重复的逻辑提取，缩小问题规模。

4.1 递归终止条件

按照之前的说明，递归应该是有去有回的，这样递归就必须有一个明确的分界点，递归可以在什么时候结束。程序一旦达到这个临界点，就不用继续递归重复下去了。简单来说，递归的终止条件就是为了防止出现无限递归的情况。

4.2 递归终止时的处理方法

如前面说到递归需要一个终止条件一样，在达到递归的终止条件时，需要有一个对应终止条件的程序处理方法。一般而言，在达到递归的终止条件时，对应的问题都是很容易解决的，可以快速的给出问题的解决方案。

4.3 递归中重复的逻辑提取，缩小问题规模

递归的本质上还是要将一个大的问题分解成各个逻辑相同的小问题，所以递归过程中一个重要的步骤就是提取递归中重复的逻辑规则，以便利用相同的处理方式进行处理。

按照以上递归的三要素，递归程序的一般处理可以总结成下面的伪代码：

recursion(big_problem){
   if (end_condition){  //满足递归的终止条件
       solve_end_condition;  //处理终止条件下的逻辑
       end;  //递归结束
   }else {
       recursion(small_problem);  //递归中重复的逻辑提取，缩小问题规模
   }
}

5. 递归的应用场景

在日常的生活学习中，递归算法一般可以用来解决很多实际问题。回顾一下我们之前学习的排序算法，其中快速排序利用了递归的思想进行解决。总而言之，递归在很多场景中都有应用。

比如说一个常见的对于操作系统里面删除指定路径下的文件夹里内容以及子文件夹里面内容的操作，就可以利用递归思想完成。这个时候递归的终止条件就是判断当前路径是文件，就可以直接删除；发现当前路径是文件夹，则递归调用方法，进入文件夹内部删除里面的文件内容。

总而言之，递归问题在现实学习科研中经常会遇到，这是一种解决问题的思路与方法，将大问题拆分成小问题，然后求解小问题之后回归归纳，得出整个问题的求解结果。

6. 小结

本节主要介绍了递归的定义及基本概念，在学完本节课程之后，需要明白递归的基础逻辑是什么样的，如何自己去设计一个递归算法，在设计一个递归算法时需要考虑到哪些问题，以及我们日常中常见的递归问题。