関数再帰とスタックの関係

まず,逆アセンブリ言語により,最も簡単な再帰関数とスタックの関係を理解する.
逆アセンブリ言語を取得する方法は、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
",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
",fact);
00DB1FFB  mov         esi,esp 
00DB1FFD  mov         eax,dword ptr [fact] 
00DB2000  push        eax  
00DB2001  push        offset string "%d
" (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://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 Factorial
");
	scanf("%d",&NOfFact);
	while(NOfFact)
	{
		Push(pStackNode,NOfFact--);
	}
	while(pStackNode->top)
	{
		Pop(pStackNode,&tmp);
		Sum *= tmp;
	}
	printf("sum is %d
",Sum);
	return 0;
}

メインプログラム部分のみが表示されます.メインプログラムでは、まずパラメータをスタックに入れます.つまり、n、n-1、...1スタックに入ってから、スタックを出て操作します.
この文章の比較的要約は,逆アセンブリ言語における階乗の再帰実現に関する実行過程と手順を見ることで,関数再帰とスタックに対する理解を深めることができることを示したい.アセンブリ言語はちょっと難しいですが、上記のブログを読むことで、みんなが読めると信じています.