摘要
本文将主要介绍递归。学好递归要多刷题，本文末尾给出了一些经典题目，做完这些题对理解递归有很大的帮助。
递归
递归的含义很好理解，就是一个函数
调用自身
，难就难在如何确定一个题目的递归式，这就需要多刷题了。
一个完整的递归函数包含两个部分:
递归式
递归出口
以斐波那契数列为例:
int f(int n){
if(n == 1 || n == 2) return 1; // 递归出口
return f(n-1) + f(n-2); // 递归式
}
递归式用来递归计算我们想要得到的值， 递归出口用来结束递归。
如果没有递归出口，那么就会一直递归下去，就造成了死循环。
那么什么题会用到递归呢？
子问题和原问题求解方式完全相同的，可以用递归。
举个例子：
蓝桥杯练习系统 计算n阶行列式
计算n阶行列式
给定一个N×N的矩阵A，求|A|。
输入格式：
第一行一个正整数N。 接下来N行，每行N个整数，
第i行第j个数字表示A[i][j]。
输出格式 一行，输出|A|。
行列式计算规则详见：
计算n阶行列式
A
1
1
A
1
2
…A
1
n
A
2
1
A
2
2
…A
2
n
…
A
n
1
A
n
2
…A
n
n
n==2 :
∣
A
∣
=
A
11
∗
A
22
−
A
12
∗
21
|A| = A_{11}~ * A_{22} – A_{12}*_{21}
∣
A
∣
=
A
1
1
∗
A
2
2
−
A
1
2
∗
2
1
n > 2 :
∣
A
∣
=
(
−
1
)
1
+
1
∗
A
11
∗
∣
A
′
∣
+
(
−
1
)
1
+
2
∗
A
12
∗
∣
A
′
∣
+
.
.
.
+
(
−
1
)
i
−
1
A
1
n
∗
∣
A
′
∣
|A| = (-1)^{1+1} * A_{11} * |A’ | + (-1)^{1+2} * A{12} * |A’ | + … + (-1)^i-1^A~1~~n~*|A’ |
∣
A
∣
=
(
−
1
)
1
+
1
∗
A
1
1
∗
∣
A
′
∣
+
(
−
1
)
1
+
2
∗
A
1
2
∗
∣
A
′
∣
+
.
.
.
+
(
−
1
)
i
−
1
A
1
n
∗
∣
A
′
∣
其中， A’ 是原矩阵
删去第 1 行和第 i 列
后构成的新矩阵。
以下面的行列式为例：
A B C
D E F = A * E F + B * D F + C * D E
G H I H I G I G H
所以当n == 2时就是递归出口了， n > 2 递归计算。
代码：
import java.io.*;
public class 计算行列式{
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
public static int Int(String s){return Integer.parseInt(s);}
public static void copy(int[][]A, int[][] A1, int i, int len) throws IOException{
for(int x = 1; x < len; x++)
for(int y = 0, j = 0; j < len; j++)
if(j != i) {
A1[x-1][y++] = A[x][j];
}
}
public static int F(int[][] A, int len)throws Exception{
int res = 0; //保存每个矩阵的|A|
if(len == 1)return A[0][0];
if(len == 2){
return A[0][0]*A[1][1] - A[0][1]*A[1][0]; // 递归出口
}
else{
int A1[][] = new int[10][10];
for(int i = 0; i < len; i++){
copy(A, A1, i, len);
res += Math.pow(-1, i) * A[0][i] * F(A1, len-1); //递归式
}
}
return res;
}
public static void main(String[] args) throws Exception{
int n;
n = Integer.parseInt(in.readLine());
int arr[][] = new int[10][10];
for(int i = 0; i < n; i++){
String[] s = in.readLine().split(" ");
for(int j = 0; j < n; j++){
arr[i][j] = Int(s[j]);
}
}
out.write(F(arr, n) + "\n");
out.flush();
}
}
练习题目
下面的练习题目是几类常见的递归题目。
代码：
1
import java.io.*;
import java.util.*;
public class Main{
static int n;
static Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
public static void f(int u, int state) throws IOException{
if(u == n){
for(int i = 1; i <= n; i++){
if((state & (1<<i)) > 0){
out.write(i+" ");
}
}
out.write("\n");
return ;
}
f(u+1, state);
f(u+1, state | (1 << (u+1)));
}
public static void main(String[] args) throws IOException{
n = in.nextInt();
f(0, 0);
out.flush();
}
}
2
import java.io.*;
import java.util.*;
public class Main{
static int n, m;
static Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
public static void f(int v, int u, int state) throws IOException{
if(u > n) return ;
if(v == m){
for(int i = 1; i <= n; i++){
if((state>>i & 1) == 1)
out.write(i+" ");
}
out.write("\n");
out.flush();
return ;
}
f(v+1, u+1, state | (1<<(u+1)));
f(v, u+1, state);
}
public static void main(String[] agrs)throws IOException{
n = in.nextInt();
m = in.nextInt();
f(0, 0, 0);
out.flush();
}
}
3
import java.io.*;
public class Main {
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
static int arr[] = new int[10];
static int n = 0;
public static void dfs(int i, int state) throws IOException{
if(i == n + 1){
for(int j = 1; j <= n; j++){
out.write(arr[j]+" ");
}
out.write("\n");
out.flush();
}
for(int j = 1; j <= n; j ++){
if((state >> j & 1) != 1){
arr[i] = j;
dfs(i+1, state | 1<<j);
}
}
}
public static void main(String[] args) throws IOException{
String s = in.readLine();
n = Integer.parseInt(s);
dfs(1, 1);
out.flush();
}
}
4
import java.io.*;
public class Main {
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
static final int N = 10;
static int a[] = new int[N];
static int dg[] = new int[2*N];
static int udg[] = new int[2*N];
static int n = 0;
public static void dfs(int i, int state) throws IOException{
if(i == n + 1){
for(int j = 1; j <= n; j++){
for(int l = 1; l <= n; l++){
if(l != a[j]) out.write(".");
else out.write("Q");
}
out.write("\n");
}
out.write("\n");
out.flush();
return;
}
for(int j = 1; j <= n; j ++){
if((state >> j & 1) != 1 && dg[i+j] != 1 && udg[j-i+n] != 1){
a[i] = j;
dg[i+j] = 1;
udg[j-i+n] = 1;
dfs(i+1, state | 1<<j);
dg[i+j] = 0;
udg[j-i+n] = 0;
}
}
}
public static void main(String[] args) throws IOException{
String s = in.readLine();
n = Integer.parseInt(s);
dfs(1, 1);
out.flush();
}
}
基础算法合集
：
https://blog.csdn.net/GD_ONE/article/details/104061907