** The article begins with the official account of WeChat ： Geometric thinking **

Recursion is a method of solving complex problems by repeated operations .

### 1. One dimensional recursion

#### 1.1 Problem description

There is one \(n\) The stairs on the first floor , You can only climb up at a time 1 Layer or 2 layer , Ask after climbing \(n\) How many different ways are there ？

#### 1.2 analysis

set up \(f(n)\) Express \(n\) There are totally different ways of building .

Let's say it's in the second \(i\) layer , Because you can only climb every time 1 Layer or 2 layer , So by the end of \(i\) Layer only 2 Ways of planting .

- From \(i-1\) Climb up the floor .
- From \(i-2\) Climb up the floor .

So the recurrence formula is \(f(n)=f(n-1)+f(n-2)\). front 2 The sum of terms is equal to 3 term , It's actually the Fibonacci sequence ,

\(1, 1, 2, 3, 5, 8, 13, 21 \cdots \cdots\)

#### 1.3 Code implementation

```
f[0] = 1; f[1] = 1;
for (int i = 2; i < n; i++){
f[i] = f[i - 1] + f[i - 2]
}
cout << f[n - 1] << endl;
```

#### 1.4 Space optimization

The recursion of each step is only related to the previous 2 It's about , So just before recording 2 The number of steps , Using the scrolling array , Instead of driving \(o(n)\) Space .

** Manual assignment **

```
int f[3];
f[0] = 1;
f[1] = 1;
for (int i = 2; i < 10; ++i) {
f[2] = f[1] + f[0];
f[0] = f[1];
f[1] = f[2];
cout << f[2] << endl;
}
```

** Take the mold and roll **

```
int f[3];
f[0] = 1;
f[1] = 1;
for (int i = 2; i < 10; ++i) {
f[i % 3] = f[(i - 1) % 3] + f[(i - 2) % 3];
cout << f[i % 3] << endl;
}
```

If it's only related to the previous state , such as \(f[n]=f[n-1]+1\), It can be used 0,1 rolling , This is more commonly used in dynamic programming .

```
int f[2], t = 0;
f[0] = 1;
for (int i = 2; i < 10; ++i) {
t = 1 - t;
f[t] = f[1 - t] + 1;
cout << f[t] << endl;
}
```

The biggest difference between recursive and dynamic programming ： Each step of recursion is the sum of all the schemes , And dynamic programming in every step of recursion , Need to use max,min To choose an optimal strategy . In fact, the essence is to deduce large-scale results through repeated small-scale model problems .

#### 1.5 Time optimization

The recurrence formula of Fibonacci sequence is very simple , But when the data is big , It's less efficient , Because recursion is \(O(n)\) Complexity .

Through matrix formula transformation, addition can be changed into multiplication

Let's put the recurrence formula into the matrix as follows ：

\(
\begin {bmatrix}1&1\\1&0\end {bmatrix}
\times
\begin{pmatrix}f(n-1) \\ f(n-2)\end{pmatrix}
=\begin{pmatrix}f(n-1)+f(n-2) \\ f(n-1)\end{pmatrix}
=\begin{pmatrix}f(n) \\ f(n-1)\end{pmatrix}
\)

hypothesis ：

\(A=\begin {bmatrix}1&1\\1&0\end {bmatrix}\)

be :

\(A^n \times
\begin{pmatrix}f(1) \\ f(0)\end{pmatrix}
= \begin{pmatrix}f(n+1) \\ f(n)\end{pmatrix}
\)

\(A^n\) It can be solved quickly by matrix power multiplication , The time complexity is \(log_2N\), And then we can get the sequence value by bringing in the above formula .

See another article for details Recursive optimization - Matrix power multiplication

### 2. Multidimensional recursion

#### 2.1 Problem description

Starting from the origin , It's going east at a time , To the north , Go west , And you can't go where you've been , Ask to leave \(n\) How many different ways are there ？

#### 2.2 analysis

Let's assume that we have reached the third stage \(i\) Step , Because you can't walk where you've been , The way that this step can go is only related to the previous step . Because one step at a time , Make sure you don't go back , Just make sure you don't go where you've been .

Every time 3 A choice , To the East , To the north , To the West .

- The first \(i-1\) Step East , So the first \(i\) We can only go north 、 To the east .
- The first \(i-1\) Step West , So the first \(i\) We can only go north 、 To the West .
- The first \(i-1\) Step North , So the first \(i\) Step North 、 To the east , To the West .

One dimensional \(f[n]\) Only one total can be recorded , Instead of recording the State , So one more dimension is needed to record the state of the last step .

set up \(f[n][0],f[n][1],f[n][2]\) respectively ： The first \(n\) Step East 、 To the West 、 There are different ways to go north .

Then there is the following recurrence relation ：

- \(f[n][0] = f[n - 1][0] + f[n - 1][2];\)
- \(f[n][1] = f[n - 1][1] + f[n - 1][2];\)
- \(f[n][2] = f[n - 1][0] + f[n - 1][1] + f[n - 1][2];\)

#### 2.3 Code implementation

```
int f[100][3] = {0};
f[0][0] = 1;
f[0][1] = 1;
f[0][2] = 1;
for (int i = 1; i < n; ++i) {
f[i][0] = f[i - 1][0] + f[i - 1][2];
f[i][1] = f[i - 1][1] + f[i - 1][2];
f[i][2] = f[i - 1][0] + f[i - 1][1] + f[i - 1][2];
}
cout << f[n - 1][0] + f[n - 1][1] + f[n - 1][2] << endl;
```

#### 2.4 Further optimization

Set the first \(n\) The total number of steps is \(s[n], s[n]=f[n][0]+f[n][1]+f[n][2]\).

\(s[n]=2\times f[n-1][0]+2\times f[n-1][1]+3\times f[n-1][2]\).

\(s[n]=2\times s[n-1]+f[n-1][2]\).

and \(f[n-1][2]=f[n-2][0]+f[n-2][1]+f[n-2][2]=s[n-2]\).

have to \(s[n]=2\times s[n-1]+s[n-2]\).

So the formula is distorted , It can also be done recursively in one dimension , But this relationship cannot be constructed directly through modeling .

### 3. Graph recursion

#### 3.1 Problem description

In a \(n\times m\) In a two-dimensional map of , A person goes from the upper left corner to the lower right corner , You can only go right or down at a time , How many different ways to get to the end ？

#### 3.2 analysis

Suppose you're already in a position , Because you can only go right or down , The last step can only come from the top or from the left .

set up \(f[i][j]\) It means to go to the coordinates \((i,j)\) The total number of programs .

be \(f[i][j]=f[i-1][j]+f[i][j-1]\).

#### 3.3 Code implementation

```
int f[10][10] = {0};
f[0][0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (i - 1 >= 0) {
f[i][j] += f[i - 1][j];
}
if (j - 1 >= 0) {
f[i][j] += f[i][j - 1];
}
}
}
```

#### 3.4 Further reflection

To get to the end , Be sure to go down \(n-1\) Step , turn right \(m-1\) Step .

Put each step together to see , In fact, the problem is equivalent to \(n+m-2\) Choose in the step \(n-1\) Step down , Or choose \(m-1\) Step right , Through permutation and combination formula \(C_{n+m-2}^{n-1}\) You can get the results directly .

### 4. State compression recursion

#### 4.1 Problem description

In a \(n\times n\) Put pieces on your chessboard , There are some places that can't be placed . It is required to place the pieces at will 2 A piece can't be in the same 1 Line or same as 1 Column , Question placement \(k\) How many different ways are there for a chess piece ？

#### 4.2 analysis

For each 1 A place , There will only be 2 In this case , Is to put or not to put . In the case of small data scale, you can use DFS( Depth-first search ) Just enumerate all the cases .

Is there a better way ？

This is ultimately the total number of required solutions , It's not necessary to consider whether you need to choose the best in each step , So it's consistent with the recursive model , The next step is to find out the recurrence relationship .

Let's first analyze some implied laws , Make things clearer ：

- Every time 1 OK or every 1 Columns can only be placed 1 A chess piece , So enumerate the placement methods on each line .
- In trying the second \(i\) Line time , Every position \((i,j)\) Can you place it , It's not just about keeping up with the industry , It's about all the previous lines . This means that you need to record the method you placed before , That is the state .

How to record the status of the scheme placed before , This requires state compression .

** State compression **： The essence is to record the corresponding position in binary system 2 States ,0 I won't let go ,1 It means to put .

about \(n\) A place , You can use it \(2^n\) A decimal number to represent all the placement schemes .

Go back to the question above , In trying the second \(i\) Line time , Can you place it with the previous \(i-1\) It's all about business , It means that you need to record the status of all previous rows placed .

But look below 2 In this case , chart 1 Sum graph 2 For trying to place 3 Line time , It's actually equivalent , front 2 Columns cannot be placed . That is to say 2 The number of schemes can be combined directly , Because each 1 There can only be one column , So the placed scheme states can also be directly merged into one line .

use \(f[i][j]\) Before presentation \(i\) That's ok , The placement scheme is \(j\) The total number of programs .

The first 0 The process is as follows ：

The first 1 The process is as follows ：

So we can deduce \(n\) That's ok ,\(2^n\) The total number of placement schemes ,\(f[n][2^n]\). Because it can only be placed \(k\) A chess piece , So in \(2^n\) It's just that \(k\) A chess plan , That is, the corresponding state \(j\) When converted to binary , Yes \(k\) individual 1.

#### 4.3 Tips ： How to find the corresponding binary inclusion of decimal number quickly 1 How many are there ?

Target number \(n\), adopt \(n \& (n-1)\) operation , How many are included 1 Just how many times the operation is performed , You can quickly find out 1 The number of .

#### 4.4 Code implementation

Calculation \(n\) Contained in the 1 The number of

```
int countOne(int n) {
int total = 0;
while (n > 0) {
total++;
n &= n - 1;
}
return total;
}
```

Variable definition and initialization

```
int i, n, k, line[8], f[2][256], num[256];
for (i = 0; i < 256; ++i) num[i] = countOne(i);
memset(f, 0, 2 * 256 * 4);
f[0][0] = 1;
int j, c, now = 0;
// The chessboard reads
for (i = 0; i < n; ++i) {
int t = 0;
for (int j = 0; j < n; ++j) {
t <<= 1;
cin >> ch;
if (ch == '.') t += 1;
}
line[i] = t;
}
```

Core recursion

```
for (i = 0; i < n; ++i) {
now = 1 - now;
for (j = 0; j < 256; ++j)
if (num[j] <= k) {
// The first i You can't let go of the pieces
f[now][j] += f[1 - now][j];
// The first i All right, put the pieces
for (c = 0; c < n; ++c) {
if ((j & 1 << c) == 0 && (line[i] & 1 << c) == 0) {
f[now][j | 1 << c] += f[1 - now][j];
}
}
}
}
// Enumerate all the objects that contain k The number of chess pieces
int ans = 0;
for (i = 0; i < 256; ++i) {
if (num[i] == k) {
ans += f[now][i];
}
}
cout << ans << endl;
```

### 5. summary

The most important idea of recursion , It's through every little step , Find out the relationship with the next step . The key is to think about the nature of the problem , Model the problem . Commonly used \(f[i][j][k]\) And so on , One more dimension can record one-dimensional state information , Think about how many factors in the previous step will affect the current step , Generally, these are the information that must be recorded .

** Scan the bottom two dimensional code to pay attention to the official account , Get updated information at the first time ！**