程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> 函數遞歸與棧的關系

函數遞歸與棧的關系

編輯:關於C

 

首先通過反匯編語言,我們來了解一下最簡單的遞歸函數與棧之間的關系。

如何獲得反匯編語言,在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寄存器中保存相乘的值。

其實在整個過程中,牽涉到函數調用中棧幀的一系列操作, /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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved