Recursion refers to a method by which a function directly or indirectly calls itself. It can usually transform a complex large-scale problem into a small-scale problem similar to the original problem.
The recursive strategy only needs a small number of programs to describe the multiple repeated calculations required in the problem-solving process, so the amount of code of the program is greatly reduced.

8.1 recursive strategy

Two conditions are required to form recursion:

1. The subproblem must be the same as the original problem and smaller.
2. You cannot call itself indefinitely. You must have a recursive exit.

Example 8.1 factorial of n

Submission URL
Recursive method:

#include <iostream>
using namespace std;

long long Factorial(int n){
	if(n == 1){
		return 1;
	}
	return n * Factorial(n - 1);
} 

int main(){
	int n;
	while(scanf("%d", &n) != EOF){
		printf("%lld\n", Factorial(n)); 		
	}
	return 0;
}

Circulation method:

#include <iostream>
using namespace std;

int main(){
	int n;
	while(scanf("%d", &n) != EOF){
		long long factorial = 1;
		while(n >= 1){
			factorial *= n--;
		}
		printf("%lld\n", factorial);
	}
	return 0;
}

Example 8.2 tower of Hanoi III

Hanoi tower is a classic recursive problem. This problem has made some changes to the problem to deepen the understanding of recursion.

#include <iostream>
using namespace std;

int Hanoi(int n){
	if(n == 1){
		return 2;
	}
	return 3 * Hanoi(n - 1) + 2;
}

int main(){
	int n;
	while(scanf("%d", &n) != EOF){
		printf("%lld\n", Hanoi(n));
	}
	return 0;
}

Exercise 8.1 Yang Hui triangle

Submission URL It is easier to think of the method of circulation.
Outrageous. How can the use case of niuke.com be so outrageous! It's not the first time that examples and test cases are different.
To start the output from the second line, the 1 of the first line is not output.

#include <iostream>
using namespace std;

long long a[1000][1000];

int main(){
	int n;
	while(scanf("%d", &n) != EOF){
		for(int i=0; i<n; i++){
			a[i][0] = a[i][i] = 1;
		}
		for(int i=2; i<n; i++){
			for(int j=1; j<i; j++){
				a[i][j] = a[i-1][j-1] + a[i-1][j];
			}
		}
		for(int i=1; i<n; i++){
			int j;
			for(j=0; j<i; j++){
				printf("%lld ", a[i][j]);
			}
			if(j == i){
				printf("%lld\n", a[i][j]);
			}
		}
	}
	return 0;
}

Exercise 8.2 full arrangement

Submission URL
c + + has next_permutation library is very suitable for this problem.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main(){
	string str, tmp;
	while(cin >> str){
		sort(str.begin(), str.end());
		do{
			cout << str << endl;
		}while(next_permutation(str.begin(), str.end()));
		printf("\n");
	}
	return 0;
}

If you do not use this function, it is similar to depth first search. As follows:

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

bool used[30];
string out = "";
string str;

void dfs(int k, int n){
	if(k == n){
		cout << out << endl;
	}else{
		for(int i=0; i<n; i++){
			if(!used[i]){
				out += str[i];
				used[i] = true;
				dfs(k+1, n);
				out = out.substr(0, out.size() - 1);
				used[i] = false;
			}
		}
	}
}

int main(){
	while(cin >> str){
		sort(str.begin(), str.end());
		memset(used, false, sizeof(used));
		dfs(0, str.length());
	}
	return 0;
}

8.2 divide and conquer method

The steps of divide and conquer are as follows:

1. Points: decompose the problem into smaller subproblems.
2. Governance: break these smaller sub problems one by one.
3. Combination: merge the solved sub problems to finally obtain the solution of the "parent" problem.

Example 8.3 Fibonacci

Submission URL

#include <iostream>
using namespace std;

int main(){
	int Fib[31];
	Fib[0] = 0;
	Fib[1] = 1;
	for(int i=2; i<=30; i++){
		Fib[i] = Fib[i-1] + Fib[i-2];
	}
	int n;
	while(scanf("%d", &n) != EOF){
		printf("%d\n", Fib[n]);
	}
	return 0;
}

Example 8.4 binary tree

Submission URL

#include <iostream>
using namespace std;

int m, n, cnt;
void dfs(int k){
	if(k > n) return;
	cnt++;
	dfs(2 * k);
	dfs(2 * k + 1);
} 

int main(){
	while(scanf("%d%d", &m, &n) != EOF){
		if(m == 0 && n == 0) break;
		cnt = 0;
		dfs(m);
		printf("%d\n", cnt);
	}
	return 0;
}

Exercise 8.3 power of 2

Submission URL
This question really knocked me out... It's AC at last.
Why 2 can't use 2 (1) to express woo woo, I can't tell which 2 is which 2. You still don't have enough skills

#include <iostream>
#include <string>
using namespace std;

string ToString(int num){
	if(num == 1){
		return "2(0)";
	}else if(num == 2){
		return "2";
	}else{
		string str = "";
		while(num > 0){
			int tmp = 1, i;
			for(i=0; tmp <= num; i++){
				tmp *= 2;
			}
			if(i == 1){
				str += "2(0)+";
			}else if(i == 2){
				str += "2+";
			}else{
				str += "2(" + ToString(i - 1) + ")+";
			}
			num -= tmp / 2;
		}
		return str.substr(0, str.size() - 1);
	}
}

int main(){
	int n;
	while(scanf("%d", &n) != EOF){
		cout << ToString(n) << endl;
	}
	return 0;
}