投稿
  1. 首页
  2. C

计算机系统——菲波拉契函数执行过程中栈帧变化情况

code • 2022-4-19 • C • 阅读 111

计算机系统——菲波拉契函数执行过程中栈帧变化情况,第1张

前言

本文内容是深入汇编层次感受递归函数栈帧变化，题目来源是hnu计算机系统讨论课。

花了大半天的时间，但是觉得很值得，对程序的机器级表示又有了更深的理解。

文章目录
  • 前言
      • 要求：
      • 分析：
      • 1.斐波那契数列1-5分别为:1 1 2 3 5
      • 2.函数调用顺序
    • 一.main函数
      • main函数栈帧准备（
    • 二.f函数
      • 2.进入f(5) f(5)->f(4)
      • 3. 进入f(4) f(4)->f(3)
      • 4. 进入f(3) f(3)->f(2)
      • 5-1.f(2)-前面的判断部分
      • 5-2.f(2)中-add esp
      • 5-3.f(2)中-pop %ebx
      • 5-4.f(2)中-pop %ebp
      • 6.返回f(3)
      • 7.返回f(3)->f(1)
      • 11.返回f(3) f(2)+f(1)
      • 12.返回f(3) f(2)+f(1)
      • 13.返回f(3) f(2)+f(1)
      • 14.返回f(4) f(4)->f(2)
      • 15.返回f(5) f(5)->f(3)
      • 16.进入f(3) f(3)->f(2)
      • 17.进入f(2)
      • 18.返回f(3) f(3)->f(1)
      • 19.返回f(5)
      • 20.返回main
      • 21.调用输出函数
  • 尾言

提示：以下是本篇文章正文内容，下面案例可供参考
题目：

小学生小军在学习递归的概念后，很轻松的写出了求菲波拉契数列的c语言代码：

#include"stdio.h"

int f(int n)

{

  if (n<=0) return 0;

  if (n==1 || n==2) return 1;

  return f(n-1)+f(n-2);

}

int main()

{

  int i=f(5);

  printf("%d\n",i);

  return 0;

}

在得知某些计算机专业的大学生要很费劲才能写出这个程序后，他很骄傲自满，为了让小军明白计算机专业知识的博大精深，我们决定向小军演示整个函数执行过程中栈帧变化情况。

要求：

从进入main函数开始到结束，每一次函数调用都至少有一个栈帧的示意图，并标注栈顶、栈底，局部变量，参数，旧ebp，返回地址等内容。

分析： 1.斐波那契数列1-5分别为:1 1 2 3 5 2.函数调用顺序

一.main函数 
gdb -q fib
b main
r
diassem
ni
si

main函数栈帧准备（

开辟栈空间，5是待传递的参数，放到栈顶

将返回地址放到栈顶，esp下移4个字节

地址内存空间标记
0xbffff138old ebp%ebp
…
0xbffff1105
0xbffff10c0x0804847f%esp

二.f函数

此时进入f函数

2.进入f(5) f(5)->f(4)
地址内存空间标记
0xbffff138old ebp
…
0xbffff1105
0xbffff10c0x0804847f(返回地址)
0xbffff1080xbffff138(old ebp)%ebp
0xbffff1040xb7fc0000(ebx)
…
0xbffff0f04
0xbffff0ec0x08048452(返回地址)%esp

3. 进入f(4) f(4)->f(3)
地址内存空间标记
0xbffff138old ebp
…
0xbffff1105
0xbffff10c0x0804847f(返回地址)
0xbffff1080xbffff138(old ebp)
0xbffff1040xb7fc0000(ebx)
…
0xbffff0f04
0xbffff0ec0x08048452(返回地址)
0xbffff0e80xbffff108(old ebp)%ebp
0xbffff0e40xb7fc0000(ebx)
…
0xbffff0d03
0xbffff0cc0x08048452(返回地址)%esp

4. 进入f(3) f(3)->f(2)
地址内存空间标记
0xbffff138old ebp
…
0xbffff1105
0xbffff10c0x0804847f(返回地址)
0xbffff1080xbffff138(old ebp)
0xbffff1040xb7fc0000(ebx)
…
0xbffff0f04
0xbffff0ec0x08048452(返回地址)
0xbffff0e80xbffff108(old ebp)
0xbffff0e40xb7fc0000(ebx)
…
0xbffff0d03
0xbffff0cc0x08048452(返回地址)
0xbffff0c80xbffff0e8(old ebp)%ebp
0xbffff0c40xb7fc0000(ebx)
…
0xbffff0bc2
0xbffff0ac0x08048452(返回地址)%esp

5-1.f(2)-前面的判断部分
地址内存空间标记
0xbffff138old ebp
…
0xbffff1105
0xbffff10c0x0804847f(返回地址)
0xbffff1080xbffff138(old ebp)
0xbffff1040xb7fc0000(ebx)
…
0xbffff0f04
0xbffff0ec0x08048452(返回地址)
0xbffff0e80xbffff108(old ebp)
0xbffff0e40xb7fc0000(ebx)
…
0xbffff0d03
0xbffff0cc0x08048452(返回地址)
0xbffff0c80xbffff0e8(old ebp)
0xbffff0c40xb7fc0000(ebx)
…
0xbffff0bc2
0xbffff0ac0x08048452(返回地址)
0xbffff0a80xbffff0c8(old ebp)%ebp
0xbffff0a40xb7fc0000(ebx)
0xbffff0901%esp
5-2.f(2)中-add esp

地址内存空间标记
0xbffff138old ebp
…
0xbffff1105
0xbffff10c0x0804847f(返回地址)
0xbffff1080xbffff138(old ebp)
0xbffff1040xb7fc0000(ebx)
…
0xbffff0f04
0xbffff0ec0x08048452(返回地址)
0xbffff0e80xbffff108(old ebp)
0xbffff0e40xb7fc0000(ebx)
…
0xbffff0d03
0xbffff0cc0x08048452(返回地址)
0xbffff0c80xbffff0e8(old ebp)
0xbffff0c40xb7fc0000(ebx)
…
0xbffff0bc2
0xbffff0ac0x08048452(返回地址)
0xbffff0a80xbffff0c8(old ebp)%ebp
0xbffff0a40xb7fc0000(ebx)%esp
0xbffff0901

5-3.f(2)中-pop %ebx

地址内存空间标记
0xbffff138old ebp
…
0xbffff1105
0xbffff10c0x0804847f(返回地址)
0xbffff1080xbffff138(old ebp)
0xbffff1040xb7fc0000(ebx)
…
0xbffff0f04
0xbffff0ec0x08048452(返回地址)
0xbffff0e80xbffff108(old ebp)
0xbffff0e40xb7fc0000(ebx)
…
0xbffff0d03
0xbffff0cc0x08048452(返回地址)
0xbffff0c80xbffff0e8(old ebp)
0xbffff0c40xb7fc0000(ebx)
…
0xbffff0bc2
0xbffff0ac0x08048452(返回地址)
0xbffff0a80xbffff0c8(old ebp)%ebp %esp
0xbffff0901

5-4.f(2)中-pop %ebp

地址内存空间标记
0xbffff138old ebp
…
0xbffff1105
0xbffff10c0x0804847f(返回地址)
0xbffff1080xbffff138(old ebp)
0xbffff1040xb7fc0000(ebx)
…
0xbffff0f04
0xbffff0ec0x08048452(返回地址)
0xbffff0e80xbffff108(old ebp)
0xbffff0e40xb7fc0000(ebx)
…
0xbffff0d03
0xbffff0cc0x08048452(返回地址)
0xbffff0c80xbffff0e8(old ebp)%ebp
0xbffff0c40xb7fc0000(ebx)
…
0xbffff0bc2
0xbffff0ac0x08048452(返回地址)%esp
0xbffff0901

6.返回f(3)

地址内存空间标记
0xbffff138old ebp
…
0xbffff1105
0xbffff10c0x0804847f(返回地址)
0xbffff1080xbffff138(old ebp)
0xbffff1040xb7fc0000(ebx)
…
0xbffff0f04
0xbffff0ec0x08048452(返回地址)
0xbffff0e80xbffff108(old ebp)
0xbffff0e40xb7fc0000(ebx)
…
0xbffff0d03
0xbffff0cc0x08048452(返回地址)
0xbffff0c80xbffff0e8(old ebp)%ebp
0xbffff0c40xb7fc0000(ebx)
…
0xbffff0b02%esp
0xbffff0ac0x08048452(返回地址)
…
0xbffff0901

7.返回f(3)->f(1)

地址内存空间标记
0xbffff138old ebp
…
0xbffff1105
0xbffff10c0x0804847f(返回地址)
0xbffff1080xbffff138(old ebp)
0xbffff1040xb7fc0000(ebx)
…
0xbffff0f04
0xbffff0ec0x08048452(返回地址)
0xbffff0e80xbffff108(old ebp)
0xbffff0e40xb7fc0000(ebx)
…
0xbffff0d03
0xbffff0cc0x08048452(返回地址)
0xbffff0c80xbffff0e8(old ebp)%ebp
0xbffff0c40xb7fc0000(ebx)
…
0xbffff0b01
0xbffff0ac0x08048462(返回地址)%esp
…
0xbffff0901

11.返回f(3) f(2)+f(1)

a

地址内存空间标记
0xbffff138old ebp
…
0xbffff1105
0xbffff10c0x0804847f(返回地址)
0xbffff1080xbffff138(old ebp)
0xbffff1040xb7fc0000(ebx)
…
0xbffff0f04
0xbffff0ec0x08048452(返回地址)
0xbffff0e80xbffff108(old ebp)
0xbffff0e40xb7fc0000(ebx)
…
0xbffff0d03
0xbffff0cc0x08048452(返回地址)
0xbffff0c80xbffff0e8(old ebp)%ebp
0xbffff0c40xb7fc0000(ebx)
…
0xbffff0b01
0xbffff0ac0x08048462(返回地址)%esp
…
0xbffff0901

b

地址内存空间标记
0xbffff138old ebp
…
0xbffff1105
0xbffff10c0x0804847f(返回地址)
0xbffff1080xbffff138(old ebp)
0xbffff1040xb7fc0000(ebx)
…
0xbffff0f04
0xbffff0ec0x08048452(返回地址)
0xbffff0e80xbffff108(old ebp)
0xbffff0e40xb7fc0000(ebx)
…
0xbffff0d03
0xbffff0cc0x08048452(返回地址)
0xbffff0c80xbffff0e8(old ebp)%ebp
0xbffff0c40xb7fc0000(ebx)
…
0xbffff0b01%esp
0xbffff0ac0x08048462(返回地址)
…
0xbffff0901
12.返回f(3) f(2)+f(1)
地址内存空间标记
0xbffff138old ebp
…
0xbffff1105
0xbffff10c0x0804847f(返回地址)
0xbffff1080xbffff138(old ebp)
0xbffff1040xb7fc0000(ebx)
…
0xbffff0f04
0xbffff0ec0x08048452(返回地址)
0xbffff0e80xbffff108(old ebp)
0xbffff0e40xb7fc0000(ebx)
…
0xbffff0d03
0xbffff0cc0x08048452(返回地址)
0xbffff0c80xbffff0e8(old ebp)%ebp
0xbffff0c40xb7fc0000(ebx)%esp
…
0xbffff0b01
0xbffff0ac0x08048462(返回地址)
…
0xbffff0901

13.返回f(3) f(2)+f(1)
地址内存空间标记
0xbffff138old ebp
…
0xbffff1105
0xbffff10c0x0804847f(返回地址)
0xbffff1080xbffff138(old ebp)
0xbffff1040xb7fc0000(ebx)
…
0xbffff0f04
0xbffff0ec0x08048452(返回地址)
0xbffff0e80xbffff108(old ebp)%ebp
0xbffff0e40xb7fc0000(ebx)
…
0xbffff0d03
0xbffff0cc0x08048452(返回地址)%esp
0xbffff0c80xbffff0e8(old ebp)
0xbffff0c40xb7fc0000(ebx)
…
0xbffff0b01
0xbffff0ac0x08048462(返回地址)
…
0xbffff0901

14.返回f(4) f(4)->f(2)
地址内存空间标记
0xbffff138old ebp
…
0xbffff1105
0xbffff10c0x0804847f(返回地址)
0xbffff1080xbffff138(old ebp)
0xbffff1040xb7fc0000(ebx)
…
0xbffff0f04
0xbffff0ec0x08048452(返回地址)
0xbffff0e80xbffff108(old ebp)%ebp
0xbffff0e40xb7fc0000(ebx)
…
0xbffff0d02
0xbffff0cc0x08048462(返回地址)%esp*
0xbffff0c80xbffff0e8(old ebp)
0xbffff0c40xb7fc0000(ebx)
…
0xbffff0b01
0xbffff0ac0x08048462(返回地址)
…
0xbffff0901
15.返回f(5) f(5)->f(3)
地址内存空间标记
0xbffff138old ebp
…
0xbffff1105
0xbffff10c0x0804847f(返回地址)%ebp
0xbffff1080xbffff138(old ebp)
0xbffff1040xb7fc0000(ebx)
…
0xbffff0f03
0xbffff0ec0x08048452(返回地址)%esp
0xbffff0e80xbffff108(old ebp)
0xbffff0e40xb7fc0000(ebx)
…
0xbffff0d01
0xbffff0cc0x08048452(返回地址)
0xbffff0c80xbffff0e8(old ebp)
0xbffff0c40xb7fc0000(ebx)
…
0xbffff0b01
0xbffff0ac0x08048462(返回地址)
…
0xbffff0901
16.进入f(3) f(3)->f(2)
地址内存空间标记
0xbffff138old ebp
…
0xbffff1105
0xbffff10c0x0804847f(返回地址)
0xbffff1080xbffff138(old ebp)
0xbffff1040xb7fc0000(ebx)
…
0xbffff0f03
0xbffff0ec0x08048452(返回地址)
0xbffff0e80xbffff108(old ebp)&ebp
0xbffff0e40xb7fc0000(ebx)
…
0xbffff0d02
0xbffff0cc0x08048452(返回地址)%esb
0xbffff0c80xbffff0e8(old ebp)
0xbffff0c40xb7fc0000(ebx)
…
0xbffff0b01
0xbffff0ac0x08048462(返回地址)
…
0xbffff0901
17.进入f(2)
地址内存空间标记
0xbffff138old ebp
…
0xbffff1105
0xbffff10c0x0804847f(返回地址)
0xbffff1080xbffff138(old ebp)
0xbffff1040xb7fc0000(ebx)
…
0xbffff0f03
0xbffff0ec0x08048452(返回地址)
0xbffff0e80xbffff108(old ebp)
0xbffff0e40xb7fc0000(ebx)
…
0xbffff0d02
0xbffff0cc0x08048452(返回地址)
0xbffff0c80xbffff0e8(old ebp)%ebp
0xbffff0c40xb7fc0000(ebx)
…
0xbffff0b01%esp
0xbffff0ac0x08048462(返回地址)
…
0xbffff0901
18.返回f(3) f(3)->f(1)
地址内存空间标记
0xbffff138old ebp
…
0xbffff1105
0xbffff10c0x0804847f(返回地址)
0xbffff1080xbffff138(old ebp)
0xbffff1040xb7fc0000(ebx)
…
0xbffff0f03
0xbffff0ec0x08048452(返回地址)
0xbffff0e80xbffff108(old ebp)%ebp
0xbffff0e40xb7fc0000(ebx)
…
0xbffff0d01
0xbffff0cc0x08048452(返回地址)%esp
0xbffff0c80xbffff0e8(old ebp)
0xbffff0c40xb7fc0000(ebx)
…
0xbffff0b01
0xbffff0ac0x08048462(返回地址)
…
0xbffff0901
19.返回f(5)
地址内存空间标记
0xbffff138old ebp
…
0xbffff1105
0xbffff10c0x0804847f(返回地址)
0xbffff1080xbffff138(old ebp)%ebp
0xbffff1040xb7fc0000(ebx)
…
0xbffff0f03
0xbffff0ec0x08048452(返回地址)%esp
0xbffff0e80xbffff108(old ebp)
0xbffff0e40xb7fc0000(ebx)
…
0xbffff0d01
0xbffff0cc0x08048452(返回地址)
0xbffff0c80xbffff0e8(old ebp)
0xbffff0c40xb7fc0000(ebx)
…
0xbffff0b01
0xbffff0ac0x08048462(返回地址)
…
0xbffff0901
20.返回main

地址内存空间标记
0xbffff138old ebp%ebp
…
0xbffff12c5
…
0xbffff1145
0xbffff1100x8048530%esp
0xbffff10c0x0804847f(返回地址)
0xbffff1080xbffff138(old ebp)
0xbffff1040xb7fc0000(ebx)
…
0xbffff0f03
0xbffff0ec0x08048452(返回地址)
0xbffff0e80xbffff108(old ebp)
0xbffff0e40xb7fc0000(ebx)
…
0xbffff0d01
0xbffff0cc0x08048452(返回地址)
0xbffff0c80xbffff0e8(old ebp)
0xbffff0c40xb7fc0000(ebx)
…
0xbffff0b01
0xbffff0ac0x08048462(返回地址)
…
0xbffff0901
21.调用输出函数
地址内存空间标记
0xb7c000%ebp
…
0xbffff138old ebp
…
0xbffff12c5
…
0xbffff1145
0xbffff1100x8048530
0xbffff10c0x0804847f(返回地址)%esp
0xbffff1080xbffff138(old ebp)
0xbffff1040xb7fc0000(ebx)
…
0xbffff0f03
0xbffff0ec0x08048452(返回地址)
0xbffff0e80xbffff108(old ebp)
0xbffff0e40xb7fc0000(ebx)
…
0xbffff0d01
0xbffff0cc0x08048452(返回地址)
0xbffff0c80xbffff0e8(old ebp)
0xbffff0c40xb7fc0000(ebx)
…
0xbffff0b01
0xbffff0ac0x08048462(返回地址)
…
0xbffff0901

22.结束

地址内存空间标记
0xb7c000
…
0xbffff138old ebp%ebp
…
0xbffff12c5
…
0xbffff1145
0xbffff1100x08048530%esp
0xbffff10c0x0804847f(返回地址)
0xbffff1080xbffff138(old ebp)
0xbffff1040xb7fc0000(ebx)
…
0xbffff0f03
0xbffff0ec0x08048452(返回地址)
0xbffff0e80xbffff108(old ebp)
0xbffff0e40xb7fc0000(ebx)
…
0xbffff0d01
0xbffff0cc0x08048452(返回地址)
0xbffff0c80xbffff0e8(old ebp)
0xbffff0c40xb7fc0000(ebx)
…
0xbffff0b01
0xbffff0ac0x08048462(返回地址)
…
0xbffff0901
尾言

最大的发现是f(3)调用 f(2)产生的数据在f(3)调用f(1)是会被覆盖掉，而不是在其他的内存地址去开辟栈空间。

f(2)的返回值被保存在ebx中，供f(3)使用（return f(2)+f(1)）,其他f调用同理。

故ebx是非常重要的！压栈千万不要忽略它呀！

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/675048.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-04-19
下一篇 2022-04-19

发表评论

登录后才能评论

评论列表（0条）

保存