知识总结
在蓝桥杯历年真题中，递归与递推考点出现的次数较为高频，最为常见的递归便是斐波那契数列，下边就针对斐波那契数列来总结一下这一类题的做题方法。
我们知道形容1，2，3，5，8，13……这样，后一项等于前两项和的数列就称作斐波那契数列，而这种递归问题都可以抽象出一颗递归搜索树，我们通过递归搜索树这种形象的展示，就可以对递归或递推问题有一定的把握。
我们以求斐波那契数列第六项为例：
public static int fab(int n) { if(n==1) { return 1; }else if(n==2) { return 2; }else return fab(n-1)+fab(n-2); } public static void main(String[] args) { Scanner s=new Scanner(System.in); int n=s.nextInt(); System.out.println(fab(n)); } //13
下图为其递归搜索树：
经典例题
(acwing92)递归实现指数型枚举
原题链接
题解思路：
这一道题就可以将其抽象为一个递归问题，如果有n个数，则每一个数对应两种情况（选或不选），一个数完成后进行下一个数的判断。
可以这n个数的状态用一个长度为n的数组来记录，1表示选，2表示未选，数组遍历进行判断，最后输出结果，完成深度递归后进行回溯。
下图为用例输入3的递归搜索树：
代码实现：
import java.util.*; public class Main { static int N=16; static int[]arr=new int[N]; //为了使得第几个数与数组的第几个元素相对应，所以数组长度加一 static int n; public static void main(String[]args) { Scanner s=new Scanner(System.in); n=s.nextInt(); dfs(1);//从第一个数开始递归 } public static void dfs(int u) { if(u>n) {/*当u>n时，意味着整个数组所有元素已经进行了判断 ，接下来就是遍历数组，根据对应的状态判断其是否需要输出 */ for(int i=1;i<=n;i++) { if(arr[i]==1) { System.out.print(i+" "); } } System.out.println(); return; } arr[u]=2; dfs(u+1); //该元素状态设为未选，然后递归下一个元素 arr[u]=1; dfs(u+1); //该元素状态设为已选，然后递归下一个元素 } }
(acwing94)递归实现排列型枚举
原题链接
题解思路：
依次枚举每个位置可以放哪个数,需要参数如下：
- 1.数组(arr[N])用于存储填入的数据.
- 2.数组(boolean[N])用于判断某个数字是否可用.
- 3.目前所在位置.
代码实现：
import java.util.*; public class Main { static int n; final static int N=10; static int[]arr=new int[N]; static boolean []st=new boolean[N]; //默认为false，所以false为该数字可用，true为不可用 public static void dfs(int u) { if(u>n) {//边界打印 for(int i=1;i<=n;i++) { System.out.print(arr[i]+" "); } System.out.println(); return; } for(int i=1;i<=n;i++) { if(!st[i]) { arr[u]=i; st[i]=true; dfs(u+1); st[i]=false;//恢复现场 } } } public static void main(String[]args) { Scanner s=new Scanner(System.in); n=s.nextInt(); dfs(1); } }
(acwing93)递归实现组合型枚举
原题链接
题解思路：
题目要求为字典序排序，只要我们按照升序递归，自然输出的即为正确顺序。
下边我们以五个数中取三个数为例，来梳理一下做这类题的思路：
我们会画出这样一棵递归树，如果要通过代码实现，我们需要通过三个参数。
- 1是数组(way[N])，用于存储于其中数字，当递归到最后一位时，按序输出数组；
- 2是递归位置（u），也就是考虑当前位置去存放哪个数；
- 3是最小开始放置的数字(start)，因为题目要求是按序输出，第一个数如果是1，那么第二个数只能是比1大的数
代码实现：
import java.util.*; public class Main { final static int N=30; static int[]way=new int[N]; static int n,m; //通过设置全局变量，可以不用传参 public static void main (String[]args){ Scanner s=new Scanner(System.in); n=s.nextInt(); m=s.nextInt(); dfs(1,1);//从第一个位置开始递归，最小开始填入的数也是1 } public static void dfs(int u,int start) { //if(u+n-start<m) //return; //上边两行代码实现的是递归树剪枝的过程，当剩余的数字不足以存储在数组内时，可以提前结束递归，提高代码运行效率 if(u>m) {//边界输出 for(int i=1;i<=m;i++) { System.out.print(way[i]+" "); } System.out.println(); return; } for(int i=start;i<=n;i++) { way[u]=i;//从start开始放置数字，保证顺序 dfs(u+1,i+1);//递归到下一个节点，且strat+1 way[u]=0;//恢复现场 } } }
总结
这三种递归模型较为常见，递归可能较难为理解，但各位同学多进行思考、画图，也会慢慢掌握这种模型的。
这篇文章涉及到了指数型排列、全排列和组合型排列三种模型：
- 指数型排列就是依次枚举每个数字的情况，每个数字有选与不选两种情况，当递归到最底层时，根据判断数组中存储的每个数字选与不选的情况直接从1到n按序输出即可。
- 全排列是依次枚举每个位置可以放哪个数，设置判断数组判断每个数字是否使用，若为使用将该位置设为该数字，然后递归到下一个位置。
- 组合型排列也是依次枚举每个位置（共m个位置）放哪个数（但数的范围为start到n），因为要求按字典序，所以后一个数一定比前一个数字大，最后输出数组即可。
