前言

相信这个故事，朋友们应该都不陌生，

从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？「从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？『从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？……』」

(相关资料图)

递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。上面的故事就是一个简单的递归，当然还有斐波那契数列等等，一系列我们熟知的。

递归

递归是将原问题拆成多个子问题然后求解，递归的代码往往很短，可能进行重复求解某些问题，而​​动态规划是在递归的基础上保存了子问题的解，避免重复计算。​​下面我们通过例题来加深对递归的理解

斐波那契数列问题的递归

​​爬楼梯问题力扣​​

题目描述: 有 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 31 3 22 1 32 3 13 1 23 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 31 2 41 2 51 3 41 3 51 4 52 3 42 3 52 4 53 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 
递推
前面的递归我们是从原问题来推出子问题，递推刚好相反，递推：子问题推出原问题
递推的斐波那契
题目描述：输入一个整数N，输出这个序列的前N项。(序列为斐波那契数列）
数据范围：0
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);    }}
最后
看在博主这么努力，熬夜肝的情况下，给个免费的三连吧！