计算机程序的思维逻辑 (12) - 函数调用的基本原理

上节我们介绍了函数的基本概念,在最后我们提到了一个系统异常java.lang.StackOverflowError,栈溢出错误,要理解这个错误,我们需要理解函数调用的实现机制。本节就从概念模型的角度谈谈它的基本原理。

我们之前谈过程序执行的基本原理:CPU有一个指令指示器,指向下一条要执行的指令,要么顺序执行,要么进行跳转(条件跳转或无条件跳转)。

基本上,这依然是成立的,程序从main函数开始顺序执行,函数调用可以看做是一个无条件跳转,跳转到对应函数的指令处开始执行,碰到return语句或者函数结尾的时候,再执行一次无条件跳转,跳转会调用方,执行调用函数后的下一条指令。

但这里面有几个问题:

  • 参数如何传递?
  • 函数如何知道返回到什么地方?在if/else, for中,跳转的地址都是确定的,但函数自己并不知道会被谁调用,而且可能会被很多地方调用,它并不能提前知道执行结束后返回哪里。
  • 函数结果如何传给调用方?

解决思路是使用内存来存放这些数据,函数调用方和函数自己就如何存放和使用这些数据达成一个一致的协议或约定。这个约定在各种计算机系统中都是类似的,存放这些数据的内存有一个相同的名字,叫栈。

栈是一块内存,但它的使用有特别的约定,一般是先进后出,类似于一个桶,往栈里放数据,我们称为入栈,最下面的我们称为栈底,最上面的我们称为栈顶,从栈顶拿出数据,通常称为出栈。栈一般是从高位地址向低位地址扩展,换句话说,栈底的内存地址是最高的,栈顶的是最小的。

计算机系统主要使用栈来存放函数调用过程中需要的数据,包括参数、返回地址,函数内定义的局部变量也放在栈中。计算机系统就如何在栈中存放这些数据,调用者和函数如何协作做了约定。返回值不太一样,它可能放在栈中,但它使用的栈和局部变量不完全一样,有的系统使用CPU内的一个存储器存储返回值,我们可以简单认为存在一个专门的返回值存储器。 main函数的相关数据放在栈的最下面,每调用一次函数,都会将相关函数的数据入栈,调用结束会出栈。

以上描述可能有点抽象,我们通过一个例子来说明。

一个简单的例子

我们从一个简单例子开始,下面是代码:

这是一个简单的例子,main函数调用了sum函数,计算1和2的和,然后输出计算结果,从概念上,这是容易理解的,让我们从栈的角度来讨论下。

当程序在main函数调用Sum.sum之前,栈的情况大概是这样的:

主要存放了两个变量args和d。在程序执行到Sum.sum的函数内部,准备返回之前,即第7行,栈的情况大概是这样的:

我们解释下,在main函数调用Sum.sum时,首先将参数1和2入栈,然后将返回地址(也就是调用函数结束后要执行的指令地址)入栈,接着跳转到sum函数,在sum函数内部,需要为局部变量c分配一个空间,而参数变量a和b则直接对应于入栈的数据1和2,在返回之前,返回值保存到了专门的返回值存储器中。

在调用return后,程序会跳转到栈中保存的返回地址,即main的下一条指令地址,而sum函数相关的数据会出栈,从而又变回下面这样:

main的下一条指令是根据函数返回值给变量d赋值,返回值从专门的返回值存储器中获得。

函数执行的基本原理,简单来说就是这样。但有一些需要介绍的点,我们讨论一下。

变量的生命周期

我们在第一节的时候说过,定义一个变量就会分配一块内存,但我们并没有具体谈什么时候分配内存,具体分配在哪里,什么时候释放内存。

从以上关于栈的描述我们可以看出,函数中的参数和函数内定义的变量,都分配在栈中,这些变量只有在函数被调用的时候才分配,而且在调用结束后就被释放了。但这个说法主要针对基本数据类型,接下来我们谈数组和对象。

数组和对象

对于数组和对象类型,我们介绍过,它们都有两块内存,一块存放实际的内容,一块存放实际内容的地址,实际的内容空间一般不是分配在栈上的,而是分配在堆(也是内存的一部分,后续文章介绍)中,但存放地址的空间是分配在栈上的。

我们来看个例子,下面是代码:

这个程序也很简单,main函数新建了一个数组,然后调用函数max计算0和数组中元素的最大值,在程序执行到max函数的return语句之前的时候,内存中栈和堆的情况大概是这样的:

对于数组arr,在栈中存放的是实际内容的地址0x1000,存放地址的栈空间会随着入栈分配,出栈释放,但存放实际内容的堆空间不受影响。

但说堆空间完全不受影响是不正确的,在这个例子中,当main函数执行结束,栈空间没有变量指向它的时候,Java系统会自动进行垃圾回收,从而释放这块空间。

递归调用

我们再通过栈的角度来理解一下递归函数的调用过程,代码如下:

在factorial第一次被调用的时候,n是4,在执行到 n*factorial(n-1),即4*factorial(3)之前的时候,栈的情况大概是:

注意返回值存储器是没有值的,在调用factorial(3)后,栈的情况变为了:

栈的深度增加了,返回值存储器依然为空,就这样,每递归调用一次,栈的深度就增加一层,每次调用都会分配对应的参数和局部变量,也都会保存调用的返回地址,在调用到n等于0的时候,栈的情况是:

这个时候,终于有返回值了,我们将factorial简写为f。f(0)的返回值为1,f(0)返回到f(1),f(1)执行1*f(0),结果也是1,然后返回到f(2),f(2)执行2*f(1),结果是2,然后接着返回到f(3),f(3)执行3*f(2),结果是6,然后返回到f(4),执行4*f(3),结果是24。

以上就是递归函数的执行过程,函数代码虽然只有一份,但在执行的过程中,每调用一次,就会有一次入栈,生成一份不同的参数、局部变量和返回地址。

函数调用的成本

从函数调用的过程我们可以看出,调用是有成本的,每一次调用都需要分配额外的栈空间用于存储参数、局部变量以及返回地址,需要进行额外的入栈和出栈操作。

在递归调用的情况下,如果递归的次数比较多,这个成本是比较可观的,所以,如果程序可以比较容易的改为别的方式,应该考虑别的方式。

另外,栈的空间不是无限的,一般正常调用都是没有问题的,但像上节介绍的例子,栈空间过深,系统就会抛出错误,java.lang.StackOverflowError,即栈溢出。

小结

本节介绍了函数调用的基本原理,函数调用主要是通过栈来存储相关数据的,系统就函数调用者和函数如何使用栈做了约定,返回值我们简化认为是通过一个专门的返回值存储器存储的,我们主要从概念上介绍了其基本原理,忽略了一些细节。

在本节中,我们假设函数的修饰符都是public static,如果不是static的,则会略有差别,后续文章会介绍。

我们谈到,在Java中,函数必须放在类中,目前我们简化认为类只是函数的容器,但类在Java中远不止有这个功能,它还承载了很多概念和思维方式,在接下来的几节中,让我们一起来探索类的世界。

原文发布于微信公众号 - 老马说编程(laoma_shuo)

原文发表时间:2016-05-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AzMark

Python 学习笔记之类与实例

类 (class) 封装一组相关数据,使之成为一个整体,并使用一种方法持续展示和维护。

5310
来自专栏Python小屋

使用Python字符串的编码与解码方法实现信息加解密

代码思路很简单,字符串的encode()方法可以将其编码为字节串,在生成的字节串中插入干扰字节后无法正常解码,要想还原信息,必须清楚干扰字节的位置并删除后再使用...

33540
来自专栏程序员互动联盟

【C语言基础】内存的初始化

我们编写C语言的时候需要给变量申请一块内存区域,当我们创建一个内存区域的时候,内存中的数据十有八九是乱七八糟的(因为其他代码用过后遗留的数据并没有及时清掉) i...

39360
来自专栏冰霜之地

从 JavaScript 作用域说开去

在电脑程序设计中,作用域(scope,或译作有效范围)是名字(name)与实体(entity)的绑定(binding)保持有效的那部分计算机程序。不同的编程语言...

10730
来自专栏大闲人柴毛毛

图的邻接表示法Java版

边节点 ? 一个边节点有一条边 和 一个终止节点组成。 /** * 边节点(由一条边和一个终止节点构成) */ class ENode{ i...

36870
来自专栏我爱编程

Day12面向对象高级编程3/3

使用元类 type() class Hello(object): def hello(self,name='World!'): prin...

36170
来自专栏iOS开发攻城狮的集散地

浅谈iOS内存管理机制

25890
来自专栏猿人谷

《C++ primer》--第11章

习题11.1 algorithm头文件定义了一个count的函数,其功能类似于find。这个函数使用一对迭代器和一个值做参数,返回这个值出现次数的统计结果。编写...

20150
来自专栏C/C++基础

C++命名方式建议

一个大型项目,参与开发人员众多,每个人的编码风格迥异,为保持代码风格统一,提高代码可读性与可维护性,一个重要的约定就是命名方式。良好统一的命名方式能让我们在不需...

7440
来自专栏Python专栏

Python 面试问答 Top 25

Python 是一种解释型,交互式,面向对象的高级编程语言。和别的一些使用标点符号的语言不同,Python使用了大量的英语单词作为关键字,因而具有很好的可读性。...

13130

扫码关注云+社区

领取腾讯云代金券