chjshen 的博客
基础算法-递归&递推
chjshen 教练 LV 5 SU @ 2023-5-31 21:15:27

递归思想

前提：已经学会写递归函数。

从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程，称为递归。

递归思想：把规模大的、较难解决的问题变成规模较小的、易解决的 $\color{#3e3eee}同一$ (解决此问题的方法相同)问题。规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解（终止条件），从而得到原来问题的解。

递归的定义：在一个函数的定义中又直接或间接地调用本身。

1、问题的定义

在学递归和递推之前，首先要习惯把问题定义出来，就是把题目用编程算法的语言描述出来。

题目：求n个学生的身高a[N]的最高值。可定义问题为：用f(k)表示前k个数的最大值，求f(n)。

题目：求n个学生的成绩a[N]之和。可定义问题为：用f(k)表示前k个数的和，求f(n)。

题目：求1到n的和。可定义问题为：用f(k)表示1..k的和，求f(n)。

显然，这样的定义主要有两个特征：

用一个数学函数（或数组）来表示问题
用参数来表示问题的范围

2、问题的转化

问题定义好以后，就可以考虑把范围大的问题转化为范围小的问题。

范围不断减小，直到足够小，此时问题已经足够简单，简单到可直接得到解。

例如求1到k之和，如果只有1个数，解就是1，即f(1) = 1。

考虑问题范围k和k-1的关系，显然有f(k) = f(k-1) + k

因此题目求f(n)，转化为求f(n-1)，再转化为f(n-2)，....，最后只要求f(1)=1。

然后依次返回，在递归函数调用返回后将小问题的解计算回大问题的解

3、递归实现

递归函数可以用来解决以上问题转化的过程，如下：

int f(int k) {
  if(k==1) return 1;
  return k+ f(k-1);
}

4、递归优缺点

优点：符合人的思维方式，递归程序结构清晰，可读性，容易理解。

缺点：通过调用函数实现，当递归层数过多时，程序的效率低。

原因：在程序执行中，递归是利用堆栈来实现的。每当进入一个函数调用，栈就会增加一层栈帧，每次函数返回，栈就会减少一层栈帧。而栈不是无限大的，当递归层数过多时，就会造成 栈溢出 的后果。

5、递归的应用场合：

数据的定义形式是递归的，例如求Fibonacii数列的第n项。
数据之间的逻辑关系（即数据结构）是递归的，如树、图等的定义和操作。
某些问题虽然没有明显的递归关系或结构，但问题的解法是不断重复执行一组操作，只是问题规模由大化小，直至某个原操作（基本操作）就结束。例如：汉诺塔问题。

总结一下递归思维：

有一个对问题的定义，一般可用递归函数表示，如int f(...)
有一个最小范围的问题，可直接得到解，如f(1) = 1
依次返回，在递归函数调用返回后将小问题的解计算回大问题的解

CCFPB01E02 Pell数列

CCFPB01E03 爬楼梯

记忆递归

1、递归重复计算

递归的重要场景就是把大问题转化为小问题，直到最小问题直接返回一个解。

有时候，一个大问题要由好几个小问题组合而而成，就容易出现重复计算。

例如斐波那契数列 f(k) = f(k-1)+f(k-2)，模拟运算可知：

f(5) = f(4)+f(3)
f(4) = f(3)+f(2)
f(3) = f(2)+f(1)

会看到f(5)需要计算f(3)，f(4)也需要计算f(3)，也即f(5)里面要计算两次f(3)，如下图：

2、记忆递归

可以用一个数组来存储某个范围第一次运算的结果，之后再运算就可以直接返回数组的值，这种技巧称之为记忆递归。

例如f(5) = f(4) + f(3)：

首先会去计算f(4) = f(3)+f(2)
- 当计算完f(3)之后，就把结果存储到_f[3]
然后计算f(3)，此时可直接返回_f[3]，无需再递归计算

核心代码：

int _f[105]; //存储记忆的数组

int f(int k) {
  if(_f[k]) return _f[k];  //已经有记忆，直接返回
  ......;
  return _f[k] = f(k-1) + f(k-2);  //运算结果返回时存储起来
}

CCFPB01D03 斐波那契数列的第n项

递推思想

1、从递归到递推

利用函数递归的知识，我们把问题的范围从大转化为小，直到最小问题直接返回解，然后依次返回，在递归函数调用返回后将小问题的解计算回大问题的解。

如果我们能比较清楚的定义出问题从小到大的方向和步骤，就可以越过函数递归的环节，直接从最小问题解往大问题解转化，这个过程就叫递推。

例如－求序列a[1],...,a[n]的和：

递归：f(k) = f(k-1) + a[k]，理解：把k问题转化为k-1问题求解
递推：f[k] = f[k-1] + a[k]，理解：已知k-1问题的解，推出k问题的解

2、递推的实现

用数组来存储每个问题的解，也称为状态。

例如：用f[k]表示数组a[N]前k个的和，递推方程为：f[k] = f[k-1] + a[k]。

int f[N];
for(int i=1; i<=n; i++)
  f[i] = f[i-1] + a[i];

3、递推的理解

3.1 状态

用数组存储起来（问题的解或中间变量）的值，称之为“状态”。

其实状态可以直接参考记忆递归的_f[N]数组。

3.2 方向

递推需要有个方向，一般数组的下标从小到大就是默认的递推方向。

有时候方向会比较隐蔽，例如走迷宫的方向从左上到右下。

有时候方向需要经过特殊手段得到，比如矩阵的值从小到大的方向才能走。

3.3 递推模式

主要有两种模式：

后面的状态通过前面的状态运算得到，如f[k] = f[k-1] + a[k]
前面的状态可影响到后面的状态：如f[i+x] += f[i]

3.4 递推与递归

能递推的，一般都能递归，反之未必。递推：从已知到结果递归：从结果到已知 hnt

例题
YBTJ1206 放苹果
YBTJ1205 汉诺塔问题
C - Submask

练习题
P282 【入门】走出迷宫的方法数
NOIPJ2001A 数的计算
CSPS2019A 格雷码 (Gray Code)
CCFPB01E02 Pell数列
NOIPS2001B 数的划分

基础算法-递归&递推