前言
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
递归 Recursion 是一种很常用的算法，这种算法比较易学，他与递推 Recurrence 一直都是相辅相成的。
本文将介绍递归含义，在题库挑选例题进行讲解，讨论与递推的相同与不同。
注意：本文有一些脚注，这些脚注是用来展示评测结果图片的。
正文
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
递归定义：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
递归的定义如下：
* 将大问题持续分解成小问题
* 在小问题达到边界条件不能分割时开始进行回归过程
比如计算 5!5!5! ,把他用乘法表现出来是这样的：
5!=5×4×3×2×15! = 5 \times 4 \times 3 \times2 \times 15!=5×4×3×2×1
如果把1~4加上括号，那就成了这样：
5×(4×3×2×1)5 \times (4 \times 3 \times2 \times 1)5×(4×3×2×1)
而被括号括起来的部分刚好是 4!4!4!
而继续分割括号部分就会变成：
4×(3×2×1)4 \times (3 \times2 \times 1)4×(3×2×1)
再分割就是：
3×(2×1)3 \times (2 \times 1)3×(2×1)
最后再分割就是：
2×(1)2 \times (1)2×(1)
1!=11! = 11!=1，所以往回带，2×1=2,3×2=6,4×6=24,5×24=1202 \times1 = 2,3 \times 2 = 6,4 \times 6 = 24,5 \times 24 = 1202×1=2,3×2=6,4×6=24,5×24=120 ,所以5!=1205! = 1205!=120。
在这个例子里，5!5!5! 是大问题，4!,3!,2!,1!4!,3!,2!,1!4!,3!,2!,1!是小问题，1!=11! = 11!=1是边界条件。
注意：如果没有边界条件，就会进入死循环。
比如这段代码：
这段代码没有边界条件，在运行时就会无限递归，在达到系统的边界条件之后停止。在我们的运行结果要进行评测时，就会OLE[1]。
例题：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
* 入门难度：A29898.递归求n!
* 普及-难度：A7972.斐波那契数列
* 普及/提高-难度：A7975.斐波那契记忆化(此题是递归记忆化)
入门难度[A495.求阶乘和]：
此题我们先参考上面的例子和题目写一个递归函数:
再在main函数进行调用，所以AC代码如下：
普及-难度[A7972.斐波那契数列]：
此题我们分析斐波那契数列的特点（第nnn个数+第n+1n+1n+1个数=第n+2n+2n+2个数）需要进行“一边二”的递归，也就是f(n)=f(n−1)+f(n−2)f(n) = f(n-1)+f(n-2)f(n)=f(n−1)+f(n−2)。而根据题目所述，第111个和第222个数都为111，所以边界条件即为在n == 1 or n == 2或者说n <= 2的时候返回1。
所以我们先写出一个递归函数：
在main函数调用此函数即可，AC代码如下：
普及/提高-难度[A7975.斐波那契记忆化]：
这题有一些难度，我们先如果写出上面的代码，那么就会TLE[2]：
我们来分析一下原因：
首先，我们先拿 f(5)f(5)f(5) 举例，我们想一想就可以知道计算它需要用到的算式：
f(5)=f(4)+f(3)f(5) = f(4) + f(3)f(5)=f(4)+f(3)
f(4)=f(3)+f(2)f(4) = f(3) + f(2)f(4)=f(3)+f(2)
f(3)=f(2)+f(1)f(3) = f(2) + f(1)f(3)=f(2)+f(1)
f(1)=1,f(2)=1f(1) = 1,f(2) = 1f(1)=1,f(2)=1
所以我们可以发现，f(5)=f(4)+f(3)f(5)=f(4)+f(3)f(5)=f(4)+f(3)，函数会计算f(4)f(4)f(4)和f(3)f(3)f(3)，f(4)=f(3)+f(2)f(4) = f(3) + f(2)f(4)=f(3)+f(2)，所以f(3)f(3)f(3)会计算两次。
我们就可以利用此特性进行记忆化，首先我们定义一个数组（列表）：
接下来定义一个函数，并添加边界条件：
接下来，如果f(n)f(n)f(n)被计算过，那么我们就可以用索引取到相对应的数，如果没有计算过，其数为000，我们就可以使用没计算为000的特性检测此数是否被计算过。
最后计算没被计算过的值并返回相应值：
最后依然在main函数调用，AC代码如下：
递归与递推的相同与不同：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
相同点：
* 重复结构：递归与递推都涉及到重复的计算过程。
* 分解问题：递归通过将问题分解成子问题来求解。
不同点：
* 计算过程：递归是将问题不断拆解成更小的子问题，在达到边界条件后往前带；递推是跟据已知的初始条件和公式，一步步地计算出后续的解。
* 思维方式：递归侧重于问题结构化；而递推侧重于构造明确的数学关系式。
示例——阶乘问题：
* 递归：通过调用自己来计算阶乘 n!=n×(n−1)!n!=n×(n−1)!n!=n×(n−1)!，直到达到基本情况1!=11!=11!=1。
* 递推：过显式公式逐步计算 n!n!n! , 从 1!=11!=11!=1 开始，用n!=n×(n−1)!n!=n×(n−1)!n!=n×(n−1)! 计算。
以下是两种方法的C++代码：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. ↩︎
2. ↩︎
