前言

学习方法后，我们来学习一种特殊调用方法的方式，即递归。本篇文章将介绍什么是递归，以及递归的使用规则和注意事项，最后通过几道经典的题目来加深对递归的理解。

博客主页：KC老衲爱尼姑的博客主页

博主的github，平常所写代码皆在于此

共勉：talk is cheap, show me the code

作者是爪哇岛的新手，水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

🏆1.生活中的递归

🎲1.1永不终结的故事

老和尚不再念经了，改行讲故事了，但是这故事无限的重复开始，实在是比念经还难受。
##🎲 1.2蒙娜丽莎之蒙娜丽莎

画中蒙娜丽莎又拿了一幅蒙娜丽莎的画，所以有多少个蒙娜丽莎?你知道吗？我不知道。

以上的两个例子都有一个共同的特征：自身中又包含自身，该种思想在数学和编程中非常有用，因为有时，我们遇到的一一些问题并不太好解决，这时我们可以将一个原问题分解为多个子问题，当发现原问题与子问题有相同的解法时，我们只需要将子问题都解决，那么原问题自然也解决了。

🏆2.什么是方法递归?

定义：一个方法直接或者间接的调用自己的形式称之为递归

递归相当于数学上的 “数学归纳法”, 有一个起始条件, 然后有一个递推公式.

例如, 我们求 N!

起始条件: N = 1 的时候, N! 为 1. 这个起始条件相当于递归的结束条件.

递归公式: 求 N! , 直接不好求, 可以把问题转换成 N! => N * (N-1)!

🎲2.1递归的必要条件：

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

了解什么是递归后，我们先来看一个错误使用递归的例子，加深我们对递归的理解

print()方法，在自己的方法体里面又调用了自己，没有任何的终止条件如同老和尚给小和尚故事，永远都讲不完。而在程序中方法或者函数实在栈区开辟内存来使用的，栈的空间有限的，而该print()方法可以无限递归下去，即无限制开辟栈的内存，最终栈的空间耗尽，会发生栈溢出。

栈溢出就是递归没有设置终止条件导致死递归了，简称“死龟”。

由上述错误的例子我们可以得出一个结论，那就是递归是需要一个终点，不然就“死龟”。

我们依然使用上述代码，给print();方法传递一个参数，当该参数为1时则终止递归。

了解递归与递归使用的注意事项后，我们来使用递归做几个题目。

🎲2.3递归题目

✔2.3.1递归求 N 的阶乘

递归公式的推导

我们都知道4的阶乘是对于1至4的每个数的乘积，3的阶乘是对于1至3的每个数的乘积，从中我们会发现4的阶乘其实可以写成4乘3的阶乘，3的阶乘可以写成3乘2的阶乘，当我们发现这个规律之后便可以推导出求N的阶乘的递归公式即:N=N * (N-1)。

public class Demo2 {
    public static void main(String[] args) {
        System.out.println("请输入一个整数：");
        Scanner sc = new Scanner(System.in);
        int num=sc.nextInt();
        int ret= factor(num);
        System.out.println(ret);
    }
    public static int  factor(int n){
        if(n==1){
            return 1;
        }
        int ret=n*factor(n-1);
        return ret;
    }

}

n=1就是求N递归的终止条件也是回溯的起点，我们将上述代码通过画图的方式展开递归来分析。

红色的线为递推的过程，绿色的线为回归的过程，由图可以清晰的知道，n=1即是递归结束的条件，恰恰也是递归开始的条件。

注意

1. 每次执行到方法体中调用自己的时候，会重新进去方法从头再来。
2. 当递归回来时想要继续这行代码，所以我们使用一个变量存在这个结果。

递归递归相当于在方法体内执行一半，又重新开始了。

✔2.3.2按顺序打印一个数字的每一位(例如 123打印出 1 2 3

递归公式的推导

数字如果是一位直接输出即可，数组如果大于等于两位以上，我们可以通过/和%来得到相应数字，下面的代码至于为什么是先/，我们可以逆向思维思考，首先我们要输出123,1是最先打印出来的，而根据递归1既是终止条件也是回归的条件，只要先不断/，最后回归的时候%一下再输出才能得到123。如果还没有明白我们画图来理解。

代码

public class Demo3 {
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        System.out.println("请输入一个数：");
        int num=sc.nextInt();
        print(num);
    }
    public static void print(int n){
        if(n<10){
            System.out.print(n);
        }else{
            print(n/10);
            System.out.print(n%10);
        }
    }

}

✔2.3.3递归求 1 + 2 + 3 + … + 10

递归公式推导

我们求1到10的和，相当于要求10+1到9的和，所以我们要求1到n的和就是求n+n-1的和，即公式为n+sum(n-1).

代码

public class Demo5 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        System.out.println(sum(n));
    }

    public static  int sum(int n ){
        if(n==1){
            return 1;
        }
        return n+sum(n-1);
    }
}

✔2.3.4写一个递归方法，输入一个非负整数，返回组成它的数字之和.

例如，输入 1729, 则应该返回 1+7+2+9，它的和是19

递归公式

比如123的各个位数的之和，sum=123%10+123/10%10+123/100%10,要求n的每一位数的和n%10+sum(n/10).

代码

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

}

✔2.3.5求斐波那契数列的第 N 项

斐波那契数列介绍

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。

在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从1963年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。

递归斐波纳契数列

斐波纳契数列递推公式为F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N），F(0)=1,F(1)=1.

public class Demo6 {
    public static void main(String[] args) {
       for(int i=0;i<10;i++){
           System.out.print(  fib( i )+" ");
       }
    }
    public static  int  fib(int n ){
        if(n==0||n==1){
            return n;
        }
        int tmp=fib(n-1)+fib(n-2);
        return tmp;
    }
}

结果图

因为我们已知的数只有F(0)=0,F(1)=1.当N大于等于2时，F(n)=F(n - 1)+F(n - 2)，会一直不断，F(n)=F(n - 1)+F(n - 2)，直到F(0)=1,F(1)=1，才会回归，这样计算有大量重复的计算，当N是一个很大的数字，计算机就要重复的计算很久，为了解决重复计算的问题，我们可以使用循环来求斐波纳契数列。

循环求斐波纳契数列

我们定义三个变量，f1和f2分别标记斐波那契数数列的第一和第二项，f3先置为-1，用来记录F(n - 1)+F(n - 2)。

public class Demo7 {
    public static void main(String[] args) {
        for(int i=0;i<10;i++){
            System.out.print(fib(i)+" ");
        }
    }

    public static  int fib(int n){
        if(n<0){
            return -1;
        }
        if(n==0||n==1){
            return n;
        }
        int f1=0;
        int f2=1;
        int f3=-1;
        for(int i=2;i<=n;i++){
            f3=f1+f2;//第三项和
            f1=f2;
            f2=f3;
        }
        return f3;
    }

}

✔2.3.6汉洛塔

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

假设有三个柱子分别为A，B，C。A柱子是盘子的起始位置，B柱子是盘子的中转位置，C柱子是目标位置。我们也不先考虑64个盘子而考虑1个盘子，我们会发现只有一个盘子我们只需将A上的盘子直接搬到C柱子。

当只有1个盘子时

移动顺序：A -> C

当只有2个盘子时

移动顺序：A ->B A->C B->C

当只有3个盘子时

移动顺序： A ->C A->B C->B A->C B->A B->C A->C

通过这三种情况，我们可以得知只有一个盘子里需要移动1次，2个盘子时需要移动3次，4个盘子是需要移动7次，由此我们可以得出盘子个数(N)于移动的次数之间的关系为2的N次方-1.同时我们也可以知道当盘子数N大于等于2时，我们可以将它成2个盘子，即最底下为一个，上面N-1为一个盘子，我们会发现我们是先将N-1个盘子先通过C柱子移动B柱子，然后将最底下的盘子移动到C柱子，然后将B柱子上的盘子通过A柱子移动到C柱子。

代码思路：我们为了打印移动轨迹，我们写个move();方法， 当只有1个盘子时，直接从A移动到C，当大于等于时我们将需要使用递归将N-1盘子从A柱子通过C柱子移动到B柱子，又将B柱子上所有的盘子通过A柱子移动到C柱子。

代码

public class Demo8 {
    public static void main(String[] args) {
        int num=3;
        hanio(3,'A','B','C');

    }
    //A B C
    //A -> C
    //A ->B  A->C B->C
    // A ->C  A->B  C->B A->C  B->A B->C  A->C

    /**
     *
     * @param n  盘子个数
     * @param pos1 盘子起始位置
     * @param pos2  盘子中转位置
     * @param pos3 盘子目标位置
     */
    public static void hanio(int n,char pos1,char pos2,char pos3){
        if(n==1){
            move(pos1,pos3);
            return ;
        }
        hanio(n-1,pos1,pos3,pos2);
        move(pos1,pos3);//只剩一个盘子，直接移动
        hanio(n-1,pos2,pos1,pos3);
    }

    public static void move(char m,char n){
        System.out.print(m+"->"+n+" ");
    }
}

结果

✔2.3.1青蛙跳台阶

一只青蛙可以一次跳 1 级台阶或一次跳 2 级台阶,例如:
跳上第一级台阶只有一种跳法:直接跳 1 级即可.
跳上两级台阶,有两种跳法: 每次跳 1 级,跳两次; 或者一次跳 2 级.
问要跳上第 n 级台阶有多少种跳法?

如图1至4个台阶的跳法种数

设台阶数为n,通过n=1,n=2,n=3，我们可以发现当n>2时，第一次跳的时候有两种不同的选择，一是第一次仅仅跳1级，此时跳法数目等于后面剩下的n-1个台阶的跳法数目，即f(n-1);当第一次选择跳2级台阶时，此时跳法的数目等于后面的剩下n-2级台阶的跳法数目，即为f(n-2)。所以求n个台阶的跳法为：f(n-1)+f(n-2)。

代码

public class Demo2 {
    public static void main(String[] args) {
        for(int i=1;i<10;i++){
            System.out.print(JumpFloor(i)+" ");
        }
    }
    public static int JumpFloor(int target){
        if(target==1){
            return 1;
        }else if(target==2){
            return 2;
        }else {
            return JumpFloor(target-1)+JumpFloor(target-2);
        }
    }
}

结果

3.总结

递归解决问题的思路：把一个复杂的问题层层转换为一个与原问题相似的规模较小的子问题来求解

递归算法三要素

• 推导出递归的公式
• 递归的终点。
• 递归的方向必须走向终点，回归的起点也是终点

最后的话

各位看官如果觉得文章写得不错，点赞评论关注走一波！谢谢啦！