概述：本篇博客中并未涉及一些关于递归的基础概念与语法，而是通过几个例子来理解递归的思想与应用。
一、简述传参机制
1.一个小知识点
在Java中的传参机制分为两种。
对于基本数据类型，传递的是值，形参的改变不会对实参产生影响。
对于引用数据类型，传递的是地址，通过形参可以改变实参。
2.在main方法中调用方法时，会在栈中生成一个新的方法栈。
当方法调用结束后，就会返回。
// 写一个递归的方法来理解
public void test(int n){
if(n > 2){
test(n - 1);
}
System.out.println("n = " + n);
}
在这里也有一个坑，如果不注意或者对于递归调用理解的不透彻就会掉坑。
掉坑想法：
假设传入的参数 n 为4，n > 2,进入递归调用，此时 n = 3, n > 2,再次进入递归调用 n = 2, 此时不满足再进行递归调用的条件了，所以输出 n 的值 n = 2。程序结束。
为了更好的辅助理解，我在下面画一个JVM的内存图。
忽略画的很丑（doge）在每次递归调用的时候，都会生成一个新的方法栈。但是栈执行后就会返回，但是仍然是执行整个调用的方法在n = 2时,递归结束，输出 n = 2
但是程序并没有直接结束，而是开始返回。
所以返回到上一层，n = 3,也就导致了仍然会输出n =3
最后输出 n = 4后，程序才会完全结束返回后，没用的方法栈就会自动销毁
二、递归的几个经典问题
概述： 都是通过创建一个单独了类来保存算法
1. 斐波那契数列
此处实现输出第n项的斐波那契数
import java.util.Scanner;
public class Fibonacci {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//输出斐波那契的前n项
System.out.println("请输入想要输出斐波那契数的第n项的n:");
int n = sc.nextInt();
//对FF类实例化
FF f = new FF();
System.out.println("第" + n + "项斐波那契数为:" + f.print(n));
}
}
//定义一个类，完成斐波那契数列的具体算法
class FF{
public int print(int n){
//对于数列的前两项进行特殊处理
if (n == 1 || n == 2){
return 1;
}else if(n > 2){
return (print(n - 1) + print(n - 2));
}else{
System.out.println("error!");
return -1;
}
}
}
对于斐波那契数列很好理解，所以不进行进一步的说明啦. 2. 猴子吃桃问题
猴子吃桃子问题，从第一天开始，每天吃掉剩余量的一半加一个桃子，当到第十天没吃之前仅剩一个桃子探索第 n 天 还剩多少桃子(吃之前的剩余量)
第十天: 1个桃子第九天: (1 + 1) * 2 = 4 个桃子第八天: (4 + 1) * 2 = 10 个桃子
可以发现:(1)如果为第十天，那么改天桃子的剩余量为 1(2)如果为第 n 天，那么改天桃子的剩余量为 (第n-1天桃子的剩余量 + 1) * 2(3)对于第十天剩余的桃子数已经不满足吃一半加一个的条件了，所以超过10天提示报错
public class PeachNum {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("请输入第几天:");
int day = sc.nextInt();
//为PP类创建对象
PP p = new PP();
int res = p.peach(day);
if(res != -1){
System.out.println("第" + day + "天桃子的剩余量为: " + res);
}
}
}
class PP{
public int peach(int day){
//第十天桃子的剩余量为1个
if(day == 10){
return 1;
}else if(day >= 1 && day < 10){
return ((peach(day + 1) + 1) * 2);
}else{
System.out.println("error!");
return -1;
}
}
}
3. 老鼠走迷宫问题
迷宫问题:从起点成功走到出口视为问题解决成功的情况
public class Maze {
public static void main(String[] args) {
int [][] map = new int[6][6];
//设置四周的墙
for (int i = 0; i < 6; i++) {
map[0][i] = 1;
map[5][i] = 1;
map[i][0] = 1;
map[i][5] = 1;
}
//设置特殊障碍点
map[2][1] = 1;
map[2][2] = 1;
//调用MM方法开始
MM m = new MM();
m.remove(map, 1, 1);
//判断是否成功到达出口
if(map[4][4] == 2){
System.out.println("小老鼠已经成功的走出了迷宫!");
}else {
System.out.println("小老鼠迷路了");
}
//打印当前的迷宫
System.out.println("===老鼠走迷宫的轨迹如下: ");
for (int k = 0; k < map.length; k++) {
for (int j = 0; j < map[k].length; j++) {
System.out.print(map[k][j] + " ");
}
System.out.println();
}
}
}
class MM{
public boolean remove(int [][] map, int i, int j){
//此处参数列表我选择了三个 map代表迷宫的地图 (i, j) 代表当前的位置
if(map[4][4] == 2){
return true;
}else{
if(map[i][j] == 0){
//默认当前的位置是通路
map[i][j] = 2;
if(remove(map, (i + 1), j)){
return true;
}else if(remove(map, i, j + 1)){
return true;
}else if(remove(map, i, j - 1)){
return true;
}else if(remove(map, i - 1, j)){
return true;
}else{
map[i][j] = 3;
return false;
}
}else{
//map[i][j] = 1, 2, 3
return false;
}
}
}
}
对于大部分注释我直接写到了代码里主要分为两个部分：在主方法中利用二维数组创建一个迷宫，在MM类中去实现如何来走迷宫的算法 4. 汉诺塔问题 5. 九皇后问题
