入门级-递归与递推

# 递归思想

`前提`：已经学会写递归函数。
![dg](http://39.99.183.126:8888/file/2/dg2.jpeg)

---
考虑求 $1+2+...+100$，即求 $\sum\limits_{i=1}^{100}i$，

我们利用枚举写出代码：

```c
int sum = 0;
for(int i = 1; i <= 100; i++)
{
    sum = sum + i;
}
cout << sum << endl;
```

---
```c++
int s(int k)
{
  if(k == 1) return 1;
  return k + s(k - 1);
}
cout << s(100) << endl;
```

---
<div style="text-align:left">
从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程，称为递归。

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

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

## 1、问题的定义
<div style="text-align:left" >
在学递归和递推之前，首先要习惯把问题定义出来，就是把题目用编程算法的语言描述出来。

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

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

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

</div>
---
显然，这样的定义主要有两个特征：

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

---

## 2、问题的转化
<div style="text-align:left">
问题定义好以后，就可以考虑把范围大的问题转化为范围小的问题。
范围不断减小，直到足够小，此时问题已经足够简单，简单到可直接得到解。

例如求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。
然后依次返回，在递归函数调用返回后将小问题的解计算回大问题的解
</div>

---

## 3、递归实现

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

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

---

## 4、递归优缺点

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

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

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

---

## 5、递归的应用场合：

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

---

## 总结一下递归思想：

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

[CCFPB01E02  Pell数列](/p/CCFPB01E02)

[CCFPB01E03  爬楼梯](/p/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)，如下图：
![image](http://39.99.183.126:8888/file/2/Q25Ucpi0CC6flXja071e3.png)

---

## 2、记忆递归

- 可以用一个数组来存储某个范围第一次运算的结果，之后再运算就可以直接返回数组的值，这种技巧称之为记忆递归。
---
例如f(5) = f(4) + f(3)：

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

核心代码：

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

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

[CCFPB01D03  斐波那契数列的第n项](/p/CCFPB01D03)

---

# 递推思想

## 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](http://39.99.183.126:8888/file/2/hnt.gif)

---

|例题|
|----|
|[**YBTJ1206**  放苹果](http://39.99.183.126:8888/p/YBTJ1206)|
|[**YBTJ1205**  汉诺塔问题](http://39.99.183.126:8888/p/YBTJ1205)|
|[C - Submask](http://39.99.183.126:8888/p/abc269c)|

---

|练习题|
|-----|
|[P282 走出迷宫的方法数](http://39.99.183.126:8888/p/282)|
|[**NOIPJ2001A**  数的计算](http://39.99.183.126:8888/p/NOIPJ2001A)|
|[**CSPS2019A**  格雷码 (Gray Code)](http://39.99.183.126:8888/p/CSPS2019A)|
|[**CCFPB01E02**  Pell数列](http://39.99.183.126:8888/p/CCFPB01E02)|
|[**NOIPS2001B**  数的划分](http://39.99.183.126:8888/p/NOIPS2001B)|