首先通過反匯編語言，我們來了解一下最簡單的遞歸函數與棧之間的關系。
如何獲得反匯編語言，在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.BkJia.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
