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);
        }
    }
}