Java 关于递归的调用机制精细解读
作者:宁海没有七号公园 发布时间:2023-01-17 04:42:41
方法的递归调用
1. 基本介绍:
简单地说,递归就是方法自己调用自己,每次调用时传入不同的变量,递归有助于编程者解决复杂问题的同时让代码变得简洁,化繁为简是其核心思想。
2. 递归能解决什么问题?
各种经典数学问题,如:八皇后问题,汉诺塔(河内塔),阶乘问题,迷宫问题,青蛙跳台阶,球和篮子的问题(Google编程大赛);
各种算法中也会使用到递归思想,比如快速排序(
quick sort
),归并排序(merge sort
),二分查找(binary search
),分治算法(divide and conquer
)等;用栈解决的问题换成递归实现 --> 递归代码比较简洁;
3. 递归举例分析:
3.1 打印问题:
我们来看一哈这一段代码:
package com.recursion;
class Test{
public void test(int n) {
if (n > 2) {
test(n - 1);
}
System.out.println("n=" + n);
}
}
public class Recursion {
public static void main(String[] args) {
Test t1 = new Test();
t1.test(4); //尝试输出看看
}
}
代码截图:
运行结果:
结果分析:
为了看起来比较规范,首先我们先简单画出 JVM
内存区域 ,这里只涉及到栈空间,堆空间和方法区:
首先看到
main
方法(程序的入口),有C/C++
基础的小伙伴们应该晓得,我们知道在调用方法时,在栈空间中会创建相应的栈帧,main
方法也是一个方法,也会被其他进程调用(在Linux中main函数有_start函数调用 ,这里不在展开,感兴趣的小伙伴自行了解⑧),所以自然也会形成main
栈帧。此时new
了一个对象,此对象会在堆中创建,在栈中的引用变量会指向此堆空间,也就是保存了此对象的地址,如图。在
main
方法中调用了test
方法,所以在栈中也会创建test
栈帧,此时我们传入的n
为4,接下来判断n
大于4吗?很明显大于4,所以在test
栈中又要调用test(n-1)
,也就是调用test(3)
,既然调用了方法,那便又要在栈中创建相应的栈帧,以此类推。当调用的方法为
test(2)
时,此时判断n
大于2显然为false
,此时便要执行方法的最后一句语句,也就是sout
打印语句,此时便会先打印2,打印完2之后方法结束( * 作系统回收/资源销毁),返回到前一个调用此方法的栈帧中,也是以此类推,直到main
方法结束。具体机制见下图。
接上图~~
到这里,我们大概就能懂为啥是先打印2,再打印3,最后才打印4了。
我们再来进一步拓展一下上述问题:
源代码:
package com.recursion;
class Test{
public void test(int n) {
if (n > 2) {
test(n - 1);
} else { //唯一区别就是加了else
System.out.println("n=" + n);
}
}
}
public class Recursion {
public static void main(String[] args) {
Test t1 = new Test();
t1.test(4); //尝试输出看看
}
}
代码截图:
运行结果:
尝试自己分析一下⑧,简单来说就是if
执行了else
就不执行,else
执行了说明if
也没执行。
3.2 阶乘问题:
源代码:
package com.recursion;
class Test01 {
public int factorial(int n) {
if (n == 1) {
return 1;
} else {
return factorial(n - 1) * n;
}
}
}
public class Factorial {
public static void main(String[] args) {
Test01 test = new Test01();
int ret = test.factorial(5);
System.out.println("ret=" + ret);
}
}
运行结果:
结果分析:大体上都跟前面的打印例子差不多,都是调用自身时在栈上开辟相应的栈帧,前面忘说了,栈帧其实会二次开辟的,啥意思呢,就是说调用方法时先在栈上分配一块较大的空间,也就是栈帧,而在栈帧内部还会进行一次具体的内存划分,具体到每一个变量。每个栈帧结束后将返回值返回给上一个栈帧,以此类推就能清晰明了的弄清楚递归的调用机制。
递归的重要规则:
执行一个方法时,就创建一个相应的新的受保护的独立空间 (栈空间/栈帧);
方法的局部变量是独立的,不会相互影响,比如前面多次提到的n变量;
如果方法中使用的是引用类型变量,比如数组或者
String
类型变量,就会共享该引用类型的数据 (指向同一堆空间);递归必须向退出递归的条件逼近,否则就是无限递归,会出现栈溢出
Stack Overflow Error
,也就是死循环;当一个方法执行完毕,或者遇到
return
时,就会返回,返回的规则遵守谁调用就将结果返回给谁,同时当方法执行完毕或者返回时,该方法也就是执行完毕,还给操作系统,具体是啥时候还给操作系统这要看当时的环境;
来源:https://blog.csdn.net/b_ingram/article/details/120638507
![](https://www.aspxhome.com/images/zang.png)
![](https://www.aspxhome.com/images/jiucuo.png)
猜你喜欢
- 1.Thread的构造方法package threadAPI;public class CreateThread { publi
- 本文实例讲述了Android游戏开发学习之引擎用法。分享给大家供大家参考。具体如下:汽车引擎是汽车的心脏,其决定了汽车的性能和稳定性,是人们
- 最近在开发一个项目,需要写一个后管系统,Bootstrap是美国Twitter公司的设计师Mark Otto和Jacob Thornton合
- 一、LinkedList 的剖白大家好,我是 LinkedList,和 ArrayList 是同门师兄弟,但我俩练的内功却完全不同。师兄练的
- 一、注解@PostConstruct使用注解@PostConstruct是最常见的一种方式,存在的问题是如果执行的方法耗时过长,会导致项目在
- 笔者计划为大家介绍分布式文件系统,用于存储应用的图片、word、excel、pdf等文件。在开始介绍分布式文件系统之前,为大家介绍一下使用本
- SharedPreferences在开发过程中,数据存取是较为频繁的,今天我们来了解下android几种常见的数据存取方式。在Android
- 使用ApplicationContext获取bean对象编写一个ApplicationContextFactory工厂类public cla
- 1. 每个编译单元(文件)都只能有一个public类。即每个编译单元都有单一的公共接口,用public类实现。此时,mian()就必须要包含
- package TOOLS;import java.io.BufferedReader;import java.io.File;import
- 前言我们在项目的开发中,难免会遇到各种可预知的、不可预知的异常需要处理。每个过程都单独处理异常,系统的代码耦合度高,工作量大且不好统一,维护
- 在使用struts多模块的,找到一些小技巧和经验,与大家分享一下。 关于多module的配置就不说了,只需要用不同的config
- Condition的作用是对锁进行更精确的控制。Condition中的await()方法相当于Object的wait()方法,Conditi
- 注意:适用于springboot或者springcloud框架1.首先下载相关文件2.然后需要去启动相关的启动文件3、导入相关jar包(如果
- SpringBoot启动yaml报错报错找不到org.yaml里的一个方法10:45:54.742 [main] ERROR org.spr
- 如何调试Java程序?大家最开始学习Java,都会觉得IDE调试好高端有木有,其实很简单了。下文会尽量简单直观的教会你在Eclipse中调试
- 重写(Override)重写是子类对父类的允许访问的方法的实现过程进行重新编写, 返回值和形参都不能改变。即外壳不变,核心重写!重写的好处在
- 前言在一个名为种花家的小镇上,生活着一群热爱编程的人。他们致力于构建出高效、可维护的软件系统,而 Spring Boot 框架成为了他们的不
- 了解YMP框架YMP于2014年10月25日正式发布1.0版本,在此之前就已在实际项目中得到广泛使用,从最初仅限团队内部使用,到合作伙伴的开
- 1.应用实例需求: 演示 Spring-Boot 通过表单注册用户,并支持上传图片2.代码实现代码实现-文件上传创建 templates/u