原创:从一个最简递归函数模型来看递归的本质

sev2008

*第一次写代码分析的文章,所以第一次会详尽一点。
问题原型:
有5个人坐在一起,问第5个人多少岁?答, 比第4个人大2岁。 第4个人说他比第3个人大2岁, 第3个人说比第2个人大2岁, 第2个人比第1个人大2岁， 问第1个人时回答是10岁, 那第5个人到底多大?
// 问题原型是5个人,我们简化为3个人,虽然性质是完全一样的。
C源码:
#include <stdio.h>
int age(int n)
{
        int c;
        if(n == 1) c = 10;
        else c = age(n-1) + 2;
        return c;
}
int main(void)
{
        printf("%d", age(3));
        return 0;
}
*这个子程序, 实参为3,age函数共调用了3次。(n=5~1之间调用了3次)


VC++6.0 自带反汇编编译源码:
10:   void main()
11:   {
00401090   push        ebp  //保存ebp的寄存器变量
00401091   mov         ebp,esp  //将当前指向栈顶指针给ebp,是开辟内存空间的前奏
00401093   sub         esp,40h //开辟 40h大小的内存空间
00401096   push        ebx  //基地址保护(待确认)
00401097   push        esi  //保存记录源地址的寄存器变量, 其中的s可以看做是source
00401098   push        edi //同上, d 可以看做是destination
00401099   lea         edi,[ebp-40h]  //edi指向所开辟内存空间的顶端, 目的是为了要对开辟的内存空间实行保护操作;
0040109C   mov         ecx,10h    // 将循环次数保存到ecx中, 10h = 40h / 4
004010A1   mov         eax,0CCCCCCCCh  // eax中写入0cccccccch
004010A6   rep stos    dword ptr [edi]   //循环执行10次,向所开辟的空间写入int 3
12:       printf("%d", age(3));
004010A8   push        3  //age函数实参
004010AA   call        @ILT+0(age) (00401005)  //age函数,接收一个参数3
004010AF   add         esp,4
004010B2   push        eax  //printf参数1
004010B3   push        offset string "%d" (0042201c)  //参数2,字符串偏移
004010B8   call        printf (00401130)  //调用库函数printf
004010BD   add         esp,8    //明显的__cdecl调用约定格式;
13:   }
// 恢复环境变量
004010C0   pop         edi   
004010C1   pop         esi
004010C2   pop         ebx
004010C3   add         esp,40h
004010C6   cmp         ebp,esp
004010C8   call        __chkesp (004010f0) //堆栈检测,无需深究
004010CD   mov         esp,ebp
004010CF   pop         ebp
004010D0   ret

//age函数反汇编
2:    int age(int n)
3:    {
00401020   push        ebp  //执行3次递归调用
00401021   mov         ebp,esp
00401023   sub         esp,44h
00401026   push        ebx
00401027   push        esi
00401028   push        edi
00401029   lea         edi,[ebp-44h]
0040102C   mov         ecx,11h
00401031   mov         eax,0CCCCCCCCh
00401036   rep stos    dword ptr [edi]
4:        int c;
5:        if(n == 1) c = 10;
00401038   cmp         dword ptr [ebp+8],1  //ebp+8显然就是形参c了,这是一个明显的if指令
0040103C   jne         age+27h (00401047)  //n!=1则跳转
// n = 1 则执行下述指令;
0040103E   mov         dword ptr [ebp-4],0Ah
6:        else c = age(n-1) + 2;
00401045   jmp         age+3Ch (0040105c)
// n != 1 则执行下述指令;
00401047   mov         eax,dword ptr [ebp+8]
0040104A   sub         eax,1  //sub eax, 1 就是 n -1
0040104D   push        eax
0040104E   call        @ILT+0(age) (00401005) //在age函数内部再次调用age函数
00401053   add         esp,4
00401056   add         eax,2
00401059   mov         dword ptr [ebp-4],eax  //执行完3次调用age函数后,eax=10,ebp-4为变量c
7:        return c;
0040105C   mov         eax,dword ptr [ebp-4]
8:    }
0040105F   pop         edi
00401060   pop         esi
00401061   pop         ebx
00401062   add         esp,44h
00401065   cmp         ebp,esp
00401067   call        __chkesp (004010f0)
0040106C   mov         esp,ebp
0040106E   pop         ebp
0040106F   ret
&#61548;        假设我们传递到age函数里面的实参为3;
&#61548;        1. 首先走到004010AA   call        @ILT+0(age) (00401005) 处, f11进入age函数内部 ,观察并记录进入内部后的esp栈顶指向的值; 此时esp=0x0012ff2c , 0x0012ff2c地址指向的数据为0x004010af ,即执行完当前call后的eip的值; 这也验证了一个执行call的经典规则: push eip & jmp call;
&#61548;        进入call内部后,第一条指令 00401005   jmp         age (00401020) ,继续F10正式进入call内部,接着往下走,或者ctrl+F10走到 一个递归自调用age函数前, F11进入后,记录下当前的esp中的数据为: ss:[esp] = 0x00401053;
&#61548;        递归调用3次age函数后，执行到ret指令(第三次调用age函数中)处,此时esp=0012fe74,[esp] = 00401053 (显然是 第三次调用age函数完成后的eip值) ,恢复栈平衡后, add eax, 2 即 age(n-1)+2 。此时变量c = 10 + 2 ,反汇编代码即为: mov         dword ptr [ebp-4],eax  //ebp-4 为变量c , 0040105C   mov    eax,dword ptr [ebp-4]在这里, 说明age(2) = 12 ;我们ret处返回;
&#61548;        继续返回到 00401053 处 ,继续上一步的操作后,变量c = 10 + 2 + 2 ,age(3) = 14
&#61548;        然后我们返回到 0x004010af 处，自此走出了age函数;
&#61548;        不难发现, ret指令的运行机制就是:pop eip
&#61548;        重要:再补充一点,递归函数写起来简单,理解起来有难度,其中问题的关键在于,多次调用call之后,没有ret。 这个例子中,是连续3次 push eip ,但是都没有ret,调用后第三次后 连续ret3次, 这也就是递归的本质, 先多次递推调用函数,然后多次回推!
*ret的本质(属于段内转移):
Pop eip //将esp指向的栈顶元素弹出堆栈 存放到 eip寄存器中去;
执行完pop eip后,以一条指令执行的位置即eip执行的内存地址处开始执行;

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
od反汇编源码:
*我们跳过启动函数。
*这里我用得是吾爱破解版的原版OD,出于不同的名称修饰约定,所以事先说明下。

00401286  |.  52            push edx
00401287  |.  A1 847C4200   mov eax,dword ptr ds:[__argv]
0040128C  |.  50            push eax
0040128D  |.  8B0D 807C4200 mov ecx,dword ptr ds:[__argc]
00401293  |.  51            push ecx
//这里就是我们写的main函数的入口地址了,上面都是一些启动函数,暂时无须深究,进入;
00401294  |.  E8 71FDFFFF   call 1.0040100A
00401299  |.  83C4 0C       add esp,0C
0040129C  |.  8945 E4       mov [local.7],eax

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
(OD)main函数反汇编代码:
//显然是比vc++6.0显示的要简洁明了多了,这里我们不进行深入分析了;
00401090 >/> \55            push ebp
00401091  |.  8BEC          mov ebp,esp
00401093  |.  83EC 40       sub esp,40
00401096  |.  53            push ebx
00401097  |.  56            push esi
00401098  |.  57            push edi
00401099  |.  8D7D C0       lea edi,[local.16]
0040109C  |.  B9 10000000   mov ecx,10
004010A1  |.  B8 CCCCCCCC   mov eax,CCCCCCCC
004010A6  |.  F3:AB         rep stos dword ptr es:[edi]
004010A8  |.  6A 03         push 3
//走到004010aa处,我们看堆栈,显示0012FF30   00000003  \Arg1 = 00000003 (arg1就是形参1,这里只有1个形参),进入:
004010AA  |.  E8 56FFFFFF   call 1.00401005
004010AF  |.  83C4 04       add esp,4
004010B2  |.  50            push eax                                 ; /<%d>
004010B3  |.  68 1C204200   push 1.0042201C                          ; |format = "%d"
004010B8  |.  E8 73000000   call 1.printf                            ; \printf
004010BD  |.  83C4 08       add esp,8
004010C0  |.  5F            pop edi
004010C1  |.  5E            pop esi
004010C2  |.  5B            pop ebx
004010C3  |.  83C4 40       add esp,40
004010C6  |.  3BEC          cmp ebp,esp
004010C8  |.  E8 23000000   call 1._chkesp
004010CD  |.  8BE5          mov esp,ebp
004010CF  |.  5D            pop ebp
004010D0  \.  C3            retn

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
(OD)age函数反汇编代码:
//反汇编代码略长,但除却必要的环境保护和恢复之外,代码量已经不大了,VC++6.0的ebp看的头痛,这里有种眼前一亮的感觉!
00401020 >/> \55            push ebp
00401021  |.  8BEC          mov ebp,esp
00401023  |.  83EC 44       sub esp,44
00401026  |.  53            push ebx
00401027  |.  56            push esi
00401028  |.  57            push edi
00401029  |.  8D7D BC       lea edi,[local.17]
0040102C  |.  B9 11000000   mov ecx,11
00401031  |.  B8 CCCCCCCC   mov eax,CCCCCCCC
00401036  |.  F3:AB         rep stos dword ptr es:[edi]
//arg.1 是 形参1
00401038  |.  837D 08 01    cmp [arg.1],1
0040103C  |.  75 09         jnz short 1.00401047
//local.1 是 局部变量1
0040103E  |.  C745 FC 0A000>mov [local.1],0A
00401045  |.  EB 15         jmp short 1.0040105C
00401047  |>  8B45 08       mov eax,[arg.1]
0040104A  |.  83E8 01       sub eax,1
0040104D  |.  50            push eax
0040104E  |.  E8 B2FFFFFF   call 1.00401005
00401053  |.  83C4 04       add esp,4
00401056  |.  83C0 02       add eax,2
00401059  |.  8945 FC       mov [local.1],eax
0040105C  |>  8B45 FC       mov eax,[local.1]
0040105F  |.  5F            pop edi
00401060  |.  5E            pop esi
00401061  |.  5B            pop ebx
00401062  |.  83C4 44       add esp,44
00401065  |.  3BEC          cmp ebp,esp
00401067  |.  E8 84000000   call 1._chkesp
0040106C  |.  8BE5          mov esp,ebp
0040106E  |.  5D            pop ebp
0040106F  \.  C3            retn

*用od分析,显然难度急骤降低. 以后我们会逐渐从简单的开始, 然后会用其他工具,比如ida, 难度梯进式的反汇编分析一些更有挑战性的例子。比如在游戏中会常用到的链表、二叉树等等。
*递归的本质 就是
I.        回推阶段
II.        递推阶段

dnf375485212

沙画 呵呵

魔鬼的马桶

膜拜菊花哥