目录

方法递归

 递归的概念

 递归执行过程分析

 执行过程图

 递归练习

 递归小结

疫情当前，大家要做好防护哦。

带好口罩了嘛？

那么大家跟着Nick来学习递归的知识！

方法递归

 递归的概念

   

  一个方法在执行过程中调用自身, 就称为 "递归"。递归相当于数学上的 "数学归纳法", 有一个起始条件, 然后有一个递推公式。

     

 简单理解递归：大问题转化为小问题。因为两者处理方式是一样的。

1、要调用自己本身

2、要有一个趋近于终止的条件

3、倒推出 递归的公式（重要）

   

 例如, 我们求 N! 起始条件: N = 1 的时候, N! 为 1. 这个起始条件相当于递归的结束条件. 递归公式: 求 N! , 直接不好求, 可以把问题转换成 N! => N * (N-1)！

      

 代码示例: 递归求 N 的阶乘

import java.util.Scanner;
public class 阶乘 {
    public static void main(String[] args) {
        Scanner src =new Scanner(System.in);
        int  n = src.nextInt();
        System.out.println(Factorial(n));
    }

    public  static int Factorial(int n){
        if(n == 1){
            return 1;
        }else{
             return n*Factorial(n-1);
        }
    }
}

     

       

 递归执行过程分析

public class Demo {
    public static void main(String[] args) {
        int n = 5;
        int ret = factor(n);
        System.out.println("ret = " + ret);
    }
    public static int factor(int n) {
        System.out.println("函数开始, n = " + n);
        if (n == 1) {
            System.out.println("函数结束, n = 1 ret = 1");
            return 1;
        }
        int ret = n * factor(n - 1);
        System.out.println("函数结束, n = " + n + " ret = " + ret);
        return ret;
    }
    // 执行结果
//    函数开始, 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
}

     

 执行过程图

  

 关于 "调用栈" 方法调用的时候, 会有一个 "栈" 这样的内存空间描述当前的调用关系，称为调用栈。

      

 每一次的方法调用就称为一个 "栈帧", 每个栈帧中包含了这次调用的参数是哪些, 返回到哪里继续执行等信息。后面我们借助 IDEA 很容易看到调用栈的内容

   

 递归练习

 代码示例1 按顺序打印一个数字的每一位(例如 1234 打印出 1 2 3 4)

   

import java.util.Scanner;
//按顺序打印一个数字的每一位(例如 1234 打印出 1 2 3 4)
public class 拆分 {
    public static void main(String[] args) {
        Scanner src =new Scanner(System.in);
        int  n = src.nextInt();
        split(n);
    }
    public static void split(int n){
        if(n<10){
            System.out.print(n%10+" ");
        }else{
            split(n/10);
            System.out.print(n%10+" ");
        }
    }
}

          

      

---

 代码示例2 递归求 1 + 2 + 3 + ... + 10

      

import java.util.Scanner;

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

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

     

       

---

 代码示例3 写一个递归方法，输入一个非负整数，返回组成它的数字之和. 例如，输入 1729, 则应该返回1+7+2+9， 它的和是19。

     

import java.util.Scanner;
//写一个递归方法，输入一个非负整数，返回组成它的数字之和.
public class 拆分 {
    public static void main(String[] args) {
        Scanner src =new Scanner(System.in);
        int  n = src.nextInt();
        System.out.print(splitSum(n));
    }
    public static int splitSum(int n){
        if(n<10){
            return n;
        }else{
            return n%10+splitSum(n/10);
        }
    }
}

     

     

---

 代码示例4 求斐波那契数列的第 N 项

   

原始版本

import java.util.Scanner;

public class fbnq {
    //求斐波那契数列的第 N 项
    public static void main(String[] args) {
        Scanner src =new Scanner(System.in);
        int  n = src.nextInt();
        System.out.println(fbnq(n));
    }
    public static int fbnq(int n){
        if(n == 1 || n ==2){
            return 1;
        }else{
            return fbnq(n-1)+fbnq(n-2);
        }
    }
}

  

 当我们求 fib(40) 的时候发现, 程序执行速度极慢，原因是进行了大量的重复运算，可以使用循环的方式来求斐波那契数列问题, 避免出现冗余运算

  

改良版本

import java.util.Scanner;

public class fbnq {
    //求斐波那契数列的第 N 项
    public static void main(String[] args) {
        Scanner src =new Scanner(System.in);
        int  n = src.nextInt();
        System.out.println(fbnq1(n));
    }
    public static int fbnq1(int n){
        if(n == 1 || n==2){
            return 1;
        }else{
            int f1 = 1;
            int f2 = 1;
            int f3= 0;
            for (int i = 3; i <=n; i++) {
                f3=f1+f2;
                f1=f2;
                f2=f3;
            }
            return f3;
        }
    }
}

   

此时程序的执行效率大大提高了

---

   

 递归小结

 递归是一种重要的编程解决问题的方式。

  

 有些问题天然就是使用递归方式定义的(例如斐波那契数列, 二叉树等), 此时使用递归来解就很容易。

  

 有些问题使用递归和使用非递归(循环)都可以解决， 那么此时更推荐使用循环, 相比于递归, 非递归程序更加高效。