【JavaSE】/*基于Java语言的递归运算*/

✨hello，进来的小伙伴们，你们好呐！✨

🍊系列专栏：【JavaSE】🍱

🍎本篇内容：JavaSE部分的递归运算详解！（对准知识点阅读喔!）

🍮作者简介：一名大二即将大三的编程小白，我很平凡，学会努力！

🍻码云存放仓库gitee:https://gitee.com/king-zhou-of-java/java-se.git

✈️✈️正文开始：

🍏递归定义：一个方法在执行过程中调用自身, 就称为 "递归"。

**🍎递归的必要条件：

1. 将原问题划分成其子问题，注意：子问题必须要与原问题的解法相同。
2. 递归出口。**

🍎🍎目录

一、实例演示：递归求N的阶乘

public class fac {
    public static int factorial(int x){
        if(x<2){
            return 1;
        }
        else{
           return x * factorial(x-1);//递归调用本身
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(factorial(n));
    }
}

**🍔递归过程分析： **

*🍖🍖本题假设我们想求解5的阶乘，我们可以看到我们从main函数里面输入一个数N，这里我们输入5，随即在我们的功能函数factorial接收到参数5，接着因为if里面的条件是x<2，不满足，所以执行我们的else里面的语句，我们发现是return x * factorial(x-1);我们输入的是5，所以即 return 5 factorial(4);同理我们调用了本身这个factorial函数，传进去的参数是4，接着继续……，直到我们的参数变成1<2,那么这时递归的 “递” ，结束，开始我们的 “归”。🛥️🛥️

// 执行结果
函数开始, n = 5
函数开始, n = 4
函数开始, n = 3
函数开始, n = 2
函数开始, n = 1
函数结束, n = 1 ret = 1
函数结束, n = 2 ret = 2
函数结束, n = 3 ret = 6
函数结束, n = 4 ret = 24
函数结束, n = 5 ret = 120
ret = 120

🍶🍶运行结果：

二、 递归调用练习

🍓🍓一、递归求1+2+3+……10的和

public class result {
    public static int fun(int n){
        if(n==1){
            return 1;
        }
        return n+fun(n-1);
    }
    public static void main(String[] args) {
        Scanner scanner  = new Scanner(System.in);
        int n = scanner.nextInt();
        System.out.println(fun(n));
    }
}

🍇🍇递归的核心思想就是我们的递归体应该如何设计，本题我们想得到1+……10的和，来看我们的递归体如何设计的！

🍨运行结果：

🍊二、顺序打印一个数字的每一位

🍨问题分析：比如我们想打印1234的每一位，那么打印出来应该就是1 2 3 4那么首先就是如何判断我们输入的数字是几位数，看下面的功能代码部分，设计非常的巧妙，通过是否n>9，是->我们递归调用本身传参数 **“n/10”,**打印的结果就是 ** n%10 ** 这样肯定得到的就是我们的每一位数字！⛵⛵

public class print {
    public static void fun(int n){
        if(n>9){
            fun(n/10);
        }
        System.out.print(n%10+" ");
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        fun(n);
    }
}

🍬🍬运行结果：

🍮 三、返回一个数组成本身的数字之和

比如我们输入1234，输出就是1+2+3+4=10。

🍖🍖函数实现：

public class sum {
    public static int sumd(int num) {
        if (num < 10)
            return num;
        return num % 10 + sumd(num / 10);
    }
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(sumd(n));
    }
}

🍓🍓运行结果：

🛩️🛩️四、求解汉诺塔问题

✨定义：汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。🌯🌯

⛵⛵代码实现：

public class Hanio {
    public static void han(int n,char pos1,char pos2,char pos3){
        if(n==1){
            move(pos1,pos3);
            return;
        }
        han(n-1,pos1,pos3,pos2);
        move(pos1,pos3);
        han(n-1,pos2,pos1,pos3);
    }
    public static void move(char pos1,char pos2){

        System.out.println(pos1+"->"+pos2);
    }
    public static void main(String[] args) {

        han(3,'A','B','C');
    }
}

⛴️⛴️代码解读：通过定义我们可以了解到每次只能移动一个盘子，并且小盘子要放在大盘子上面，那么这里我们有A B C，三个圆柱，我们可以将其依次理解为：初始位置 跳板位置 目标位置，我们看函数部分，如果只有一个盘子我们直接从A->C 只需移动一步便可，那么>1的情况，这里我们假设要移动三个盘子，通过画图我们可以发现首先要将2个盘子移动到B圆柱再借助A移动到C盘，那么这里的第一次调用 han(n-1,pos1,pos3,pos2);我们便可以理解，下次递归将（n-1）作为盘子个数，pos1就是我们的起始位置，pos3就是我们的跳板位置，pos2就是我们的目标位置，因为首先我们将(n-1）个盘子放在了B（pos2）上，调用结束后，执行我们的move函数，输出我们这次的移动轨迹，下次调用就是han(n-1,pos2,pos1,pos3);同理，这个时候pos2就是我们的起始位置,pos1变成我们的跳板位置，最后pos3是我们的目标位置。🍱🍱

🍇🍇运行结果：（我们可以自己画图尝试一下看这个结果是否正确）

🍏 五、求斐波那契数列第N项

🍻🍻斐波那契数列指的是这样一个数列：1，1，2，3，5，8，13，21，34，55，89...这个数列从第3项开始，每一项都等于前两项之和。

🍼🍼那么，谈及递归的运算不得不提斐波那契数列这样的经典问题，下面就给大家展示一下Java语言的代码实现：

public class Fib {
    public static int Fibo(int n){
        if(n<=2){
            return 1;
        }
        else{
            return Fibo(n-1)+Fibo(n-2);
        }
    }
    public static void main(String[] args) {
        Scanner sc =new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(Fibo(n));
    }
}

🍱🍱代码分析：虽然这种递归方法很容易理解方便使用，但是我们发现在递归的过程中，如果我们要求斐波那契数列的前40项 50项的和，以40项为例我们首先需要求 39项 38项的结果，而要得到39项的和我们要求出38的项的结果和37项的结果，进而上个38项的结果我们需要在求一次，这样发现我们有很多次的重复计算，造成了很不必要的浪费，那么我们可以通过for循环的方式来减少代码冗余度。🧂🧂

☕☕优化代码：

public static int fib(int n) {
  int last2 = 1;
  int last1 = 1;
  int sum = 0;
  for (int i = 3; i <= n; i++) {
    sum = last1 + last2;
    last2 = last1;
    last1 =sum;
 }
  return sum;
}

🍰🍰运行结果：