【递归知识+练习】

---

递归

递归的概念

一个方法在执行过程中调用自身, 就称为 “递归”。

递归的必要条件：

1. 将原问题划分成其子问题，注意：子问题必须要与原问题的解法相同
2. 递归出口（也就是要有一定的条件让递归结束，否则会死循环）
3. 在写递归之前，想一想这个题目是否可以用递归公式解决。

♥♥♥ 栈存储的顺序：

按顺序打印一个数字的每一位

（例如1234 打印出 1 2 3 4）

public class Test {
    public static void main(String[] args) {
        print(1234);
    }
    public static void print(int n){
    //递归结束条件，满足条件后进入打印1，返回1
        if(n<10){
            System.out.println(n);//先打印再返回
            return ;
        }
        //递123，递12 再递1
        print(n/10);
        //归12打印2，归123打印3
        System.out.println(n%10);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

递归求N！的阶层

public class Test {
    public static void main(String[] args) {
        System.out.println(fac(5));
    }
    public static int fac(int n){
    //条件必不可少
        if(n==1){
            return 1;
        }
        int sum= n * fac(n-1);
        return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

递归求1+2+3+4+…+10

public class Test {
    public static void main(String[] args) {
        System.out.println(sum(10));
    }
    public static int sum(int n){
        if(n==1){
            return 1;
        }
        return n+sum(n-1);
    }
}
1
2
3
4
5
6
7
8
9
10
11

写一个递归方法，输入一个非负整数。返回组成它的数字之和（不熟）

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

public class Test {
    public static void main(String[] args) {
        System.out.println(sum(123));
    }
    public static int sum(int i){
        if (i<10){
            return i;
        }
        return i%10+sum(i/10);//3+sum(12/10) 2+sum(1)

    }
}
1
2
3
4
5
6
7
8
9
10
11
12

斐波那契数列（不熟）

//斐波那契数列
//不建议用递归写，太多重复的
//建议用for循环写

public class Test {
    public static void main(String[] args) {
        System.out.println(sum(5));
    }
    public static int sum(int n){
        int f1=1;
        int f2=1;
        int f3=2;
        if (n==1){
            return 1;
        }
        if (n==2){
            return 1;
        }
        for (int i = 3; i <= n; i++) {
               f3=f1+f2;
                f1=f2;
                f2=f3;
        }
        return f3;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

递归求汉诺塔（难点）

public class Test {
    //移动的方法，盘子是字符char类型
    public static void move(char pos1,char pos2){
        System.out.print(pos1 +" => "+ pos2 +"  ");
    }
    //方法括号里的参数有盘子个数，三根柱子
    public static void hanio(int n,char pos1,char pos2,char pos3){
        if(n==1){
            move(pos1,pos3);
            return ;
        }
        //递归，把n-1个盘子从起始位置移动到pos3，再把pos3的盘子移到pos2
       hanio(n-1,pos1,pos3,pos2);
        //把pos1的盘子移到pos3
        move(pos1,pos3);
        //把pos2的盘子移到pos1上，再把pos1的盘子移到pos3上
        hanio(n-1,pos2,pos1,pos3);

    }

    public static void main(String[] args) {
        hanio(1,'A','B','C');//第一个盘子
        System.out.println();
        hanio(2,'A','B','C');//第二个盘子
        System.out.println();
        hanio(3,'A','B','C');//第三个盘子
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

总结

今天专攻递归，写了几道题目感觉还不错，对递归的思维更深刻了。