C|从流程图和汇编代码清晰看透递归函数代码的执行流程

C|从流程图和汇编代码清晰看透递归函数代码的执行流程

首页休闲益智堆栈平衡更新时间:2024-07-31

先看下面的简单实例:

#include <stdio.h> int counts(int n) { printf("call: %d\n",n); if(n==0) return n; else { counts(n-1); printf("back: %d\n",n); return n; } } void main() { printf("%d",counts(3)); getchar(); }

运行结果:

call: 3 call: 2 call: 1 call: 0 back: 1 back: 2 back: 3

关键是明白其代码调用、回归的流程,以及其参数值是如何迭代的。

基本的流程如下:

下面从汇编的层面分析:

首先是主函数调用递归函数开始:

18: printf("%d",counts(3)); 0040D7B8 push 3 0040D7BA call @ILT 0(counts) (00401005) 0040D7BF add esp,4

call指令会完成两个动作,先是将call指令的下一条指令的地址0040D7BF压栈(push),以便返回;然后是执行一个jmp指令:

00401005 jmp counts (00401020)

跳转到函数开始处00401020,先整体看一下函数的汇编代码:

3: int counts(int n) 4: { 00401020 push ebp 00401021 mov ebp,esp 00401023 sub esp,40h 00401026 push ebx 00401027 push esi 00401028 push edi 00401029 lea edi,[ebp-40h] 0040102C mov ecx,10h 00401031 mov eax,0CCCCCCCCh 00401036 rep stos dword ptr [edi] 5: printf("call: %d\n",n); 00401038 mov eax,dword ptr [ebp 8] 0040103B push eax 0040103C push offset string "call: %d\n" (00422028) 00401041 call printf (00401110) 00401046 add esp,8 6: if(n==0) 00401049 cmp dword ptr [ebp 8],0 0040104D jne counts 34h (00401054) 7: return n; 0040104F mov eax,dword ptr [ebp 8] 00401052 jmp counts 57h (00401077) 8: else 9: { 10: counts(n-1); 00401054 mov ecx,dword ptr [ebp 8] 00401057 sub ecx,1 0040105A push ecx 0040105B call @ILT 0(counts) (00401005) 00401060 add esp,4 11: printf("back: %d\n",n); 00401063 mov edx,dword ptr [ebp 8] 00401066 push edx 00401067 push offset string "back: %d\n" (0042201c) 0040106C call printf (00401110) 00401071 add esp,8 12: return n; 00401074 mov eax,dword ptr [ebp 8] 13: } 14: } 00401077 pop edi 00401078 pop esi 00401079 pop ebx 0040107A add esp,40h 0040107D cmp ebp,esp 0040107F call __chkesp (00401190) 00401084 mov esp,ebp 00401086 pop ebp 00401087 ret

然后分开来分析:

3: int counts(int n) 4: { 00401020 push ebp 00401021 mov ebp,esp 00401023 sub esp,40h 00401026 push ebx 00401027 push esi 00401028 push edi 00401029 lea edi,[ebp-40h] 0040102C mov ecx,10h 00401031 mov eax,0CCCCCCCCh 00401036 rep stos dword ptr [edi]

进入函数后,先压栈底指针,抬高栈底指针,提升栈顶指针,压寄存器,初始化这一段栈帧空间(debug模式)。

通常是一段这样的操作:

(地址值仅供参考)

继续下面的汇编代码:

5: printf("call: %d\n",n); 00401038 mov eax,dword ptr [ebp 8] 0040103B push eax 0040103C push offset string "call: %d\n" (00422028) 00401041 call printf (00401110) 00401046 add esp,8 6: if(n==0) 00401049 cmp dword ptr [ebp 8],0 0040104D jne counts 34h (00401054) 7: return n; 0040104F mov eax,dword ptr [ebp 8] 00401052 jmp counts 57h (00401077) 8: else 9: { 10: counts(n-1); 00401054 mov ecx,dword ptr [ebp 8] 00401057 sub ecx,1 0040105A push ecx 0040105B call @ILT 0(counts) (00401005) 00401060 add esp,4

上面的cmp,在CPU内部是做一个减法,修改标志寄存器的值,根据标志寄存器的值形成跳转。

参数n减1后压栈。

递归调用函数,call指令会将地址00401060压栈,跳转到00401005。

循环上面的操作,继续抬高堆栈,直到参数值n==0:

00401049 cmp dword ptr [ebp 8],0 0040104D jne counts 34h (00401054) 7: return n; 0040104F mov eax,dword ptr [ebp 8] 00401052 jmp counts 57h (00401077)

返回:

00401077 pop edi 00401078 pop esi 00401079 pop ebx 0040107A add esp,40h 0040107D cmp ebp,esp 0040107F call __chkesp (00401190) 00401084 mov esp,ebp 00401086 pop ebp 00401087 ret

C代码的返回,在汇编层面还有一些代码要生成并被执行,就是堆栈平衡,

然后是ret,与call相对应,ret指令也是执行两个动作,pop出在call时压进栈的返回地址,执行jmp命令返回:

00401060 add esp,4 11: printf("back: %d\n",n); 00401063 mov edx,dword ptr [ebp 8] 00401066 push edx 00401067 push offset string "back: %d\n" (0042201c) 0040106C call printf (00401110) 00401071 add esp,8 12: return n; 00401074 mov eax,dword ptr [ebp 8] 13: } 14: } 00401077 pop edi 00401078 pop esi 00401079 pop ebx 0040107A add esp,40h 0040107D cmp ebp,esp 0040107F call __chkesp (00401190) 00401084 mov esp,ebp 00401086 pop ebp 00401087 ret

引用递归调用的函数参数,将返回值压到寄存器eax,堆栈平衡,再ret返回。

循环上面的操作3次,ret到最首先调用的下一个语句的地址0040D7BF:

0040D7BF add esp,4 0040D7C2 push eax 0040D7C3 push offset string "%d" (00422034) 0040D7C8 call printf (00401110) 0040D7CD add esp,8 19: getchar();

到此,递归调用完成。

存放堆栈指针的寄存器ebp、esp的值回归到原处。

-End-

查看全文
大家还看了
也许喜欢
更多游戏

Copyright © 2024 妖气游戏网 www.17u1u.com All Rights Reserved