【JavaSE】深入浅出悟透递归

简介: 文章目录1 什么是递归?2 递归的执行机制2.1 浅尝递归2.2 递归的重要规则3 递归练习3.1 练习1 斐波那契3.2 练习2 猴子吃

1 什么是递归?

✈️ 通俗点来说,递归就是让方法自己调用自己,每次调用自己时传入不同的变量。有助于将复杂的问题简单化,使代码更加简洁。


2 递归的执行机制

2.1 浅尝递归

😗 递归在内存中是如何执行的呢?其实总的来说,就一句话:谁调用还给谁的原则! 为了便于大家理解我们来看一个例子:


阅读如下代码块,猜猜控制台会输出什么?

class Recursion{
    // 递归打印函数
    public void myPrint(int n){
        if(n > 1){
            myPrint(n-1);
        }
        System.out.println("n = " + n);
    }
}
public class Exercise1 {
    public static void main(String[] args) {
        Recursion r = new Recursion();
        r.myPrint(3);
    }
}

输出结果如下:

小伙伴看到这里可能会疑惑,为什么会是这个结果?别急,我们继续从内存角度一点点分析:


  1. ⭐️ 首先程序进入 main栈,在堆区开辟一个空间用于存储对象,并让 r 指向该空间;
  2. ⭐️ 开始 调用 myPrint 方法,程序在栈区开辟出了一个 myPrint栈独立空间(橙色),传入的参数初始值为 n = 3,满足 n > 1,继续执行 myPrint(3 - 1),递归调用;
  3. ⭐️ 开辟另一个 myPrint栈空间(紫色),传入参数为 n = 2,满足 n > 1,继续执行 myPrint(2 - 1),递归调用;
  4. ⭐️ 再次开辟一个 myPrint栈空间(粉色),传入参数 n = 1,不满足 n > 1,所以执行输出 n = 1的操作后该空间进程结束,回退到 myPrint栈空间(紫色);
  5. ⭐️ 此时打印 n = 2,该空间进程结束,再次回退,返回到 myPrint栈空间(橙色);
  6. ⭐️ 此时打印 n = 3,该空间进程也结束了,于是返回到 main栈,继续执行主函数未完成的操作。

具体示意图如下:

2.2 递归的重要规则

🅰️通过以上内容,大家一定对递归有了更深入的了解,需要注意的是样例中我们传入的参数是 基本数据类型,因此,递归的各个方法产生的栈互不影响。 如果我们传入的是一个引用数据类型,则由于数据存储在堆区,则会因为方法的调用相互产生影响。具体参考博客:

1.【JavaSE】深入理解类与对象 || 方法调用机制与方法的传参机制浅析

2.【JavaSE】数组的赋值机制(值拷贝与引用传递)、数组拷贝、数组反转与数组扩容


🍑 递归所满足的规则总结如下:


  1. 执行一个方法的时候,就会 创建一个新的受保护的独立栈空间;
  2. 如果方法传入的是基本数据类型,则 局部变量是独立的,不会相互影响;
  3. 如果方法传入的是引用数据类型,比如数组,就会 共享该引用类型的数据;
  4. 当一个方法执行完毕后,或者遇到 return语句,就会返回,满足谁调用就将结果返回给谁的原则;
  5. 当方法执行完毕或者返回时,该方法的进程也将结束了。

3 递归练习

😎 说了那么多,又到了练习的环节啦!一定要自己思考后再看答案哦!!!


3.1 练习1 斐波那契

请用递归的方式求出斐波那契数列 1,1,2,3,5,8,13… …

要求:给定一个整数 n,能够求出斐波那契的第 n 项的值即可。


🍑 思路分析: 这应该算是递归的经典题型啦,我们来仔细观察一下斐波那契数列,可以发现除了第1项和第2项的值是1以外,其余各项的值 F(n) = F(n - 1) + F(n - 2),其中 n 表示第几项。


🍎 参考代码:

public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(fibonacci(4));
    }
    private static int fibonacci(int n){
        if(n == 1 || n == 2){
            return 1;
        }else {
            return fibonacci(n-1) + fibonacci(n-2);
        }
    }
}

3.2 练习2 猴子吃桃问题

有一堆桃子,猴子第一天吃掉了其中的一半,并多吃了一个!以后每天猴子都吃其中的一半,然后再多吃一个。当到第十天的时候,想再吃时(还没吃),发现桃子只剩下了1个。

问:最初桃子🍑 总数是多少?


🍑 思路分析如下:


day = 10时,只有 1 个桃子;

day = 9时,有 (day = 10 天的桃子数 + 1) * 2个桃子;

day = 8时,有(day = 9天的桃子数 + 1)* 2个桃子;

通过分析我们发现规律: 前一天的桃子数 = (后一天的桃子数 + 1)* 2

🍎 参考代码: (输出的答案为:1534)

public class Monkey {
    public static void main(String[] args) {
        System.out.println(monkeyEatPeaches(1));
    }
    private static int monkeyEatPeaches(int day){
        if(day == 10){
            return 1;
        }else if(day >= 1 && day <= 9){
            return (monkeyEatPeaches(day + 1) + 1) * 2;
        }else {
            System.out.println("输入错误");
            return -1;
        }
    }
}
相关文章
|
7月前
奇淫技巧系列第三篇:阅读源码时基于一组快捷键让我们知道身在何方!
奇淫技巧系列第三篇:阅读源码时基于一组快捷键让我们知道身在何方!
|
存储 算法
【数据结构】单链表---C语言版(全网最最最最细!小白必必必必看!!!有图有真相!)(一)
【数据结构】单链表---C语言版(全网最最最最细!小白必必必必看!!!有图有真相!)(一)
99 0
|
XML Java 数据库连接
一.最最简单,最最通俗易懂,XMl解析
一.最最简单,最最通俗易懂,XMl解析
37 0
|
算法
【数据结构】单链表---C语言版(全网最最最最细!小白必必必必看!!!有图有真相!)(二)
【数据结构】单链表---C语言版(全网最最最最细!小白必必必必看!!!有图有真相!)(二)
68 0
|
存储 算法 C语言
九分钟带你弄懂KMP算法【原理篇】
在一些寻找子串的问题中,我们常常使用的是BF算法,也就是暴力算法,这样做的时间复杂度通常都是O(N^2),且不能体现出算法的美妙之处
218 0
|
存储 编译器
IAT表入门简析【滴水逆向三期52笔记】
IAT表入门简析【滴水逆向三期52笔记】
|
机器学习/深度学习 算法 Java
Java实现递归及经典案例(不死神兔三种方式)
本文简单介绍了递归的概念和使用递归时的注意事项,并分享了求阶乘案例(两种方式)、不死神兔案例(三种方式)以及利用递归删除一个带内容的文件的案例;
261 0
|
存储 自然语言处理 算法
刚学完c没掌握完的知识,不会学c++的时候还没搞懂吧?
c++既可用于基于过程的结构化程序设计,又可用于面向对象的程序设计,是一个功能强大的混合型程序设计语言。
133 0
刚学完c没掌握完的知识,不会学c++的时候还没搞懂吧?
|
Web App开发 存储 前端开发
【番外01】吐血整理5万字100道高频基础面试题 无名面试集《烂俗前端》
【番外01】吐血整理5万字100道高频基础面试题 无名面试集《烂俗前端》
200 0
|
前端开发 JavaScript
#yyds干货盘点# 前端歌谣的刷题之路-第九十四题-数组过滤
#yyds干货盘点# 前端歌谣的刷题之路-第九十四题-数组过滤
100 0
#yyds干货盘点# 前端歌谣的刷题之路-第九十四题-数组过滤