# Thinking construction and skill realization of recursion

2021-02-05 18:05:36

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 ！

https://chowdera.com/2021/02/20210205160813540O.html