07《算法入门教程》递归算法

1. 前言

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

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

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

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

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

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

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

数学归纳法适用于将需要解决的原问题转换为解决他的子问题，而其中的子问题又可以变成子问题的子问题，而且这些问题都是同一个模型，可以用相同的处理逻辑归纳处理。当然有一个是例外的，就是归纳结束的那一个处理方法不能适用于其他的归纳处理项。递归同样的是将大的问题分解成小问题处理，然后会有一个递归的终止条件，满足终止条件之后开始回归。
数学里面有一个很有名的斐波那契数列，我们在编程求解斐波那契数列的时候就会用到递归的思想，在后续的内部中会具体讲到。
4. 递归的三要素

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

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

4.1 递归终止条件

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

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

递归的本质上还是要将一个大的问题分解成各个逻辑相同的小问题，所以递归过程中一个重要的步骤就是提取递归中重复的逻辑规则，以便利用相同的处理方式进行处理。
按照以上递归的三要素，递归程序的一般处理可以总结成下面的伪代码：