目录

方法递归

💬 递归的概念

💬 递归执行过程分析

💬 执行过程图

💬 递归练习

💬 递归小结

​

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

带好口罩了嘛？

那么大家跟着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; }    }}

   

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

---

   

💬 递归小结

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

  

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

  

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