函数递归与栈的关系

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

如何获得反汇编语言，在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("%dn",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("%dn",fact);
00DB1FFB
mov
esi,esp
00DB1FFD
mov
eax,dword ptr [fact]
00DB2000
push
eax
00DB2001
push
offset string "%dn" (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;

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)

在factorial的反汇编中，

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

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

00DB1B2A
imul
eax,dword ptr [n] 

其实在整个过程中，牵涉到函数调用中栈帧的一系列操作，http://blog.csdn.net/free2011/article/details/6868334这篇博客详细讲述了调用函数过程中栈帧的一系列操作。

进行一个总结：

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

在阶乘中，我们通过对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 Factorialn");
scanf("%d",&NOfFact);
while(NOfFact)
{
Push(pStackNode,NOfFact--);
}
while(pStackNode->top)
{
Pop(pStackNode,&tmp);
Sum *= tmp;
}
printf("sum is %dn",Sum);
return 0;
}

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

最后

以上就是天真月亮为你收集整理的函数递归与栈的关系的全部内容，希望文章能够帮你解决函数递归与栈的关系所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。