首页 > 程序开发 > 软件开发 > C语言 >

函数递归与栈的关系

2011-11-13

首先通过反汇编语言,我们来了解一下最简单的递归函数与栈之间的关系。如何获得反汇编语言,在visual studio 2008中,在debug环境下,在debug/windows/disassembly中可以查看反汇编之后的语言。现在我们看一下...

首先通过反汇编语言,我们来了解一下最简单的递归函数与栈之间的关系。

如何获得反汇编语言,在visual studio 2008中,在debug环境下,在debug/windows/disassembly中可以查看反汇编之后的语言。现在我们看一下阶乘n!的实现

其C语言实现代码如下

#include <stdio.h>

int factorial(int n);

int main(void)

{

int fact;

fact = factorial(4);

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

return 0;

}

int factorial(int n)

{

if (1 == n )

return 1;

return n * factorial(n - 1);

}

其反汇编之后的语言如下

主程序main

int main(void)

{

00DB1FD0 push ebp

00DB1FD1 mov ebp,esp

00DB1FD3 sub esp,0CCh

00DB1FD9 push ebx

00DB1FDA push esi

00DB1FDB push edi

00DB1FDC lea edi,[ebp-0CCh]

00DB1FE2 mov ecx,33h

00DB1FE7 mov eax,0CCCCCCCCh

00DB1FEC rep stos dword ptr es:[edi]

int fact;

fact = factorial(4);

00DB1FEE push 4

00DB1FF0 call @ILT+475(_factorial) (0DB11E0h)

00DB1FF5 add esp,4

00DB1FF8 mov dword ptr [fact],eax

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

00DB1FFB mov esi,esp

00DB1FFD mov eax,dword ptr [fact]

00DB2000 push eax

00DB2001 push offset string "%d\n" (0DB5A38h)

00DB2006 call dword ptr [__imp__printf (0DB82BCh)]

00DB200C add esp,8

00DB200F cmp esi,esp

00DB2011 call @ILT+320(__RTC_CheckEsp) (0DB1145h)

return 0;

其factorial函数的汇编如下

int factorial(int n)

{

00DB1AF0 push ebp

00DB1AF1 mov ebp,esp

00DB1AF3 sub esp,0C0h

00DB1AF9 push ebx

00DB1AFA push esi

00DB1AFB push edi

00DB1AFC lea edi,[ebp-0C0h]

00DB1B02 mov ecx,30h

00DB1B07 mov eax,0CCCCCCCCh

00DB1B0C rep stos dword ptr es:[edi]

if (1 == n )

00DB1B0E cmp dword ptr [n],1

00DB1B12 jne factorial+2Bh (0DB1B1Bh)

return 1;

00DB1B14 mov eax,1

00DB1B19 jmp factorial+3Eh (0DB1B2Eh)

return n * factorial(n - 1);

00DB1B1B mov eax,dword ptr [n]

00DB1B1E sub eax,1

00DB1B21 push eax

00DB1B22 call @ILT+475(_factorial) (0DB11E0h)

00DB1B27 add esp,4

00DB1B2A imul eax,dword ptr [n]

}

00DB1B2E pop edi

00DB1B2F pop esi

00DB1B30 pop ebx

00DB1B31 add esp,0C0h

00DB1B37 cmp ebp,esp

00DB1B39 call @ILT+320(__RTC_CheckEsp) (0DB1145h)

00DB1B3E mov esp,ebp

00DB1B40 pop ebp

00DB1B41 ret

在整个汇编程序中,在

call @ILT+475(_factorial) (0DB11E0h)

之前的push 为参数的入栈。这儿是关键,其他的push我们可以认为是系统为了栈的平衡而进行的必要操作。

在factorial的反汇编中,

00DB1B39 call @ILT+320(__RTC_CheckEsp) (0DB1145h)

这句话是函数factorial调用自己本身,也就是递归。

push eax;将每次入栈的参数保存到eax寄存器中,然后再入栈,这样在n != 1时,每次的参数都会入栈;

00DB1B2A imul eax,dword ptr [n]

这一步骤是为了进行相乘。在eax寄存器中保存相乘的值。

其实在整个过程中,牵涉到函数调用中栈帧的一系列操作, http://www.2cto.com/kf/201111/110912.html 这篇博客详细讲述了调用函数过程中栈帧的一系列操作。

进行一个总结:

函数递归是利用系统中栈进行操作的,通过对栈帧的一系列操作,从而实现递归。这个过程是由系统来完成的。

在阶乘中,我们通过对factorial函数的参数入栈,然后通过栈帧的一系列操作,从而实现参数的出栈,进而完成阶乘这个动作。整个过程实际上就是一个栈的入栈和出栈问题。

现在我们要通过自己定义一个栈来实现函数递归。

#include "stack.h"

#define NumOfStack 10

int main(void)

{

StackNode * pStackNode = NULL ;

int NOfFact;

int tmp = 1,Sum = 1;

pStackNode = CreateStack(NumOfStack);

printf("the number of Factorial\n");

scanf("%d",&NOfFact);

while(NOfFact)

{

Push(pStackNode,NOfFact--);

}

while(pStackNode->top)

{

Pop(pStackNode,&tmp);

Sum *= tmp;

}

printf("sum is %d\n",Sum);

return 0;

}

仅仅呈现主程序部分。在主程序中,我们首先对参数入栈,也就是对n 、n-1、...1入栈,然后再出栈进行操作。

这篇文章写的比较概括,我希望告诉大家的是,通过观看反汇编语言中关于阶乘的递归实现的运行过程及步骤,能够加深我们对于函数递归和栈的理解。虽然汇编语言有些难懂,但是通过阅读上面为大家推荐blog,相信大家都能够看懂。

摘自 yankai0219

相关文章
最新文章
热点推荐