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

一步一步寫算法(之遞歸和堆棧)

編輯:關於C

 

【 聲明:版權所有,歡迎轉載,請勿用於商業用途。  聯系信箱:feixiaoxing @163.com】

 

 

 

 

    看過我前面博客的朋友都清楚,函數調用主要依靠ebp和esp的堆棧互動來實現的。那麼遞歸呢,最主要的特色就是函數自己調用自己。如果一個函數調用的是自己本身,那麼這個函數就是遞歸函數。

 

    我們可以看一下普通函數的調用怎麼樣的。試想如果函數A調用了函數B,函數B又調用了函數C,那麼在堆棧中的數據是怎麼保存的呢?

 

 

view plaincopy to clipboardprint?函數A    ^ 

函數B    |    (地址遞減) 

函數C    | 

函數A    ^

函數B    |    (地址遞減)

函數C    |    如果是遞歸函數呢,舉一個簡單的遞歸函數為例:

 

 

view plaincopy to clipboardprint?int iterate(int value) 

    if(value == 1) 

        return 1; 

    return value + iterate(value -1); 

int iterate(int value)

{

       if(value == 1)

              return 1;

       return value + iterate(value -1);

}    下面我們使用一個函數進行調用,看看會發生什麼情況?

 

 

view plaincopy to clipboardprint?void process() 

    int value = iterate(6); 

void process()

{

       int value = iterate(6);

}    看看此時內存堆棧是什麼樣的?

 

 

view plaincopy to clipboardprint?iterate(int 1) line 96 

iterate(int 2) line 97 + 12 bytes 

iterate(int 3) line 97 + 12 bytes 

iterate(int 4) line 97 + 12 bytes 

iterate(int 5) line 97 + 12 bytes 

iterate(int 6) line 97 + 12 bytes 

process() line 102 + 7 bytes 

main() line 108 

mainCRTStartup() line 206 + 25 bytes 

KERNEL32! 7c817067() 

iterate(int 1) line 96

iterate(int 2) line 97 + 12 bytes

iterate(int 3) line 97 + 12 bytes

iterate(int 4) line 97 + 12 bytes

iterate(int 5) line 97 + 12 bytes

iterate(int 6) line 97 + 12 bytes

process() line 102 + 7 bytes

main() line 108

mainCRTStartup() line 206 + 25 bytes

KERNEL32! 7c817067()

    大家也看到了上面的代碼,遞歸函數和普通的函數也沒有什麼差別。除了自己調用本身之外,他就是一個普通的函數。那麼這個函數遞歸到什麼時候返回呢?這就是遞歸函數的關鍵了。我們看到iterate函數到1就停止了,所以上面的堆棧在(value == 1)即return。所以一個遞歸函數最關鍵的部分就是兩點:(1)遞歸策略;(2)函數出口。

 

    看到這裡,大家可能感到遞歸函數不過如此,事實上也是這樣。但是,還有一點大家需要牢記在心,遞歸的深度是我們必須考慮的一個問題。只有遞歸深度在一個可控的范圍內,那麼整個遞歸過程都是可控的。那什麼時候不可控呢?那就是遞歸深度超過了一定的數字?這個數字和具體的線程堆棧長度有關?等到堆棧溢出了,那麼獲得的數據已經失去了真實性,所以也就沒有意義了。

 

    我們把上面的問題推廣一下,如何用自己定義的堆棧模擬上面的遞歸調用呢?這樣既能滿足遞歸的屬性,又能確保函數深度可控。

 

    大家可以先寫一下自己的方案,下面只是我個人的一個思路。

 

 

view plaincopy to clipboardprint?int iterate(int value) 

    int count = 0; 

    int number  =0; 

 

    push(value); 

    while(-1 != (number = pop())) 

    { 

        if(1 != number) 

            push(number -1); 

        count += number; 

    } 

 

    return count; 

int iterate(int value)

{

       int count = 0;

       int number  =0;

 

       push(value);

       while(-1 != (number = pop()))

       {

              if(1 != number)

                     push(number -1);

              count += number;

       }

 

       return count;

}

 

 

 

 

 

 

 

【預告: 下面一篇博客介紹算法和內存】

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