前言
相信这个故事，朋友们应该都不陌生，
从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？「从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？『从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？……』」
递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。上面的故事就是一个简单的递归，当然还有斐波那契数列等等，一系列我们熟知的。
递归
递归是将原问题拆成多个子问题然后求解，递归的代码往往很短，可能进行重复求解某些问题，而动态规划是在递归的基础上保存了子问题的解，避免重复计算。下面我们通过例题来加深对递归的理解
斐波那契数列问题的递归
题目描述: 有 N 阶楼梯，每次可以上一阶或者两阶，求有多少种上楼梯的方法。
定义一个数组 dp 存储上楼梯的方法数(为了方便讨论，数组下标从 1 开始)，dp[i] 表示走到第 i 个楼梯的方法数目。第 i 个楼梯可以从第 i-1 和 i-2 个楼梯再走一步到达，走到第 i 个楼梯的方法数为走到第 i-1 和第 i-2 个楼梯的方法数之和。
思路一：直接递归
class Solution {
public int climbStairs(int n) {
if(n == 1)
return 1;
if(n == 2)
return 2;
return climbStairs(n-1) + climbStairs(n-2);
}
}
发现超时了，原因是我们对于climbStairs递归进行了重复的计算，dp的方程不难看出：
思路二：动态规划
class Solution {
public int climbStairs(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}递归实现排列型枚举
题目描述：把 1∼n 这 n个整数排成一行后随机打乱顺序，输出所有可能的次序。
输入格式：一个整数 n。
输出格式：按照从小到大的顺序输出所有方案，每行 1 个。首先，同一行相邻两个数用一个空格隔开。其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。
数据范围：1≤n≤9
输入样例：3
输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
思路：数据范围是1~9，推断可能选择的算法为，暴力递归，指数级别，dfs+剪枝
排列型枚举，依次枚举每个数放到哪个位置，从小到大枚举，肯定是字典序最小，转换为递归搜索树为：
import java.util.Scanner;
/**
* @Author 秋名山码神
* @Date 2023/1/30
* @Description
*/
public class 排列枚举每个数 {
static int N = 10;
static int n;
static int[] state = new int[N];//0表示没放数，1~n表示放了哪个数
static boolean[] used = new boolean[N];
public static void dfs(int u){
if(u>n){
for(int i = 1; i<=n; i++){
System.out.print(state[i]);
}
System.out.println();
return;
}
//依次枚举每个分支
for(int i = 1; i<=n; i++){
if(!used[i]){
state[u] = i;
used[i] = true;
dfs(u+1);
//恢复现场
state[u] = 0;
used[i] = false;
}
}
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
n = cin.nextInt();
dfs(1);//从1开始，最后打印除了就是字典序最小
}
}
递归实现组合型枚举
题目描述：
从 1~n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。
输入格式：
两个整数 n,m ,在同一行用空格隔开。
输出格式：
按照从小到大的顺序输出所有方案，每行1个。
首先，同一行内的数升序排列，相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如1 3 5 7排在1 3 6 8前面）。
数据范围：n>0，0≤m≤n ，n+(n−m)≤25
输入样例：
5 3
输出样例：
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
思路：
import java.util.Scanner;
/**
* @Author 秋名山码神
* @Date 2023/1/30
* @Description
*/
public class 组合枚举每个数 {
static int N = 30;
static int n,m;
static int[] ways = new int[N];
public static void dfs(int u,int start){
//剪枝， 如果把后面的数都选上还不够m，意味这无解，例如4开始，……
if(u+n - start <m) return;
if(u == m +1){
for(int i = 1; i<=m; i++){
System.out.print(ways[i] + " ");
}
System.out.println();
}
for(int i = start; i<=n; i++){
ways[u] = i;
dfs(u+1,i+1);
ways[u] = 0;//实际上是没有意义的，恢复现场，前面给覆盖掉了
}
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
n = cin.nextInt();
m = cin.nextInt();
dfs(1,1);
}
}
递推
前面的递归我们是从原问题来推出子问题，递推刚好相反，递推：子问题推出原问题
递推的斐波那契
题目描述：
输入一个整数N，输出这个序列的前N项。(序列为斐波那契数列）
数据范围：0<N<46
import java.util.Scanner;
/**
* @Author 秋名山码神
* @Date 2023/1/31
* @Description
*/
public class fib {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] f = new int[46];
f[1] = 0;
f[2] = 1;
for(int i = 3; i<= n; i++){
f[i] = f[i-1] + f[i-2];
}
for(int i = 1; i<=n; i++)
System.out.print(f[i]+" ");
System.out.println();
}
}
带分数
来源：第四届蓝桥杯省赛C++B/C组,第四届蓝桥杯省赛JAVAA/B组
数据范围：1 <= N < 10^6
目标是找到三个数,使得n=a+b/c,可以考虑使用暴力解法将1~9的全排列给一个个搜出来,然后每次找到一种排列,就利用二重循环将该段排列分成三段,第一段得到a,第二段得到b,第三段得到c,然后进行判断即可
优化： n是已知的，可以把等式变形为，cn = c *a + b,枚举ac，直接算出b
package 递归;
import java.util.Scanner;
/**
* @Author 秋名山码神
* @Date 2023/1/31
* @Description
*/
public class 带分数真题 {
static boolean[] st = new boolean[12];
static int[] ans = new int[12];
static int n = 100;
static int res = 0;
public static void dfs(int x)
{
if(x > 9)
{
for(int i = 1;i <= 7;i++)
for(int j = i + 1;j <= 8;j++)
{
int a = 0;
int b = 0;
int c = 0;
int cnt = 1;
for(int k = 1;k <= i;k++)
{
a += ans[k] * cnt;
cnt *= 10;
}
cnt = 1;
for(int k = i + 1;k <= j;k++)
{
b += ans[k] * cnt;
cnt *= 10;
}
cnt = 1;
for(int k = j + 1;k <= 9;k++)
{
c += ans[k] * cnt;
cnt *= 10;
}
if(b % c == 0)
{
if(a + b/c == n) {res ++;}
}
}
return;
}
for(int i = 1;i <= 9;i++)
{
if(st[i]) continue;
ans[x] = i;
st[i] = true;
dfs(x + 1);
st[i] = false;
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
dfs(1);
System.out.println(res);
}
}
翻硬币
来源：第四届蓝桥杯省赛C++B组
数据范围：n<100
暴力递归可以写
import java.util.Scanner;
/**
* @Author 秋名山码神
* @Date 2023/1/31
* @Description
*/
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String ss1 = sc.next();
String ss2 = sc.next();
char[] s1 = ss1.toCharArray();
char[] s2 = ss2.toCharArray();
int cnt = 0;
for(int i = 0; i < s1.length-1; i++){
if(s1[i] != s2[i]){
cnt++;
if(s1[i] == '*')
s1[i] = 'o';
else
s1[i] = '*';
if(s1[i+1] == '*')
s1[i+1] = 'o';
else
s1[i+1] = '*';
}
}
System.out.println(cnt);
}
}
最后
看在博主这么努力，熬夜肝的情况下，给个免费的三连吧！
