用彙編的眼光看C++（之遞歸函數與模闆類） 19

【 聲明：版權所有，歡迎轉載，請勿用于商業用途。 】

    遞歸，相信有過基本C語言經驗的朋友都明白，就是函數自己調用自己。是以，本質上說，它和普通的函數調用沒有什麼差別。今天之是以會把模闆類和遞歸聯系在一起，是因為我們可以用遞歸的方法實作模闆的遞歸。閑話不多說，我們先從一個統計函數開始說起。

[cpp] view plaincopy

1. int process(int m)  
2. {  
3.     int index = 0;  
4.     int count = 0;  
5.     assert(m >= 0);  
6.     for (; index <=m; index++){  
7.         count += index;  
8.     }  
9.     return count;  
10. }  

    上面的代碼不太難。大家可以看一下，其實就是一個和計算函數，它計算從0~m遞增的總和是多少。那麼這樣的一段代碼，用遞歸應該怎麼寫呢？大家可以自己試一下。下面的代碼是我自己的一個方案，供大家參考。

4.     if(m == 0)  
5.         return 0;  
6.     else  
7.         return process(m -1) + m;  

    我們看到，遞歸的目的就是把大的計算拆分到小的計算，最後再進行計算合并。比如說，我們計算process（5），那就需要計算 process（4）；process（4）又需要計算process（3）；process（3）又需要計算 process（2）；process（2）有需要計算process（1）；process（1）計算有需要 process（0）；process（0）就可以得到結果了，數值為0，那麼進而可以得到process（1），以此類推，最後可以得到結果 process（5）的數值。這就是遞歸處理的全過程。

    那麼，這和模闆類有什麼關系，我們可以看看下面這個範例：

1. template<int m>  
2. class calculate  
4. public:  
5.     static int process()  
6.     {  
7.         return calculate<m-1>::process() + m;  
9. };  
10. template<>  
11. class calculate<0>  

    上面這段代碼非常有意思。我們發現模闆的資料類型不再是int、double或者是自己定義的資料類型，而是一個一個具體的數字。但是每一種數字也代表 了一種類型，是以說，calculate<5>和calculate<4>就是兩種不同的類。除此之外，我們還是用到了靜态處理 函數。但是這裡的靜态函數有點特别，我們發現靜态函數process需要調用另外一個類的靜态函數，也就是calculate<m-1>的靜 态函數才能獲得結果。是以為了獲得結果，我們需要建立很多的類和很多的靜态函數。那麼，類什麼時候結束呢？我們看到了calculate下面還有一個類， 那就是calculate的特化模闆，也就是說那m=0的時候，并不再繼續向下處理了，計算開始回歸。那麼這個類怎麼應用呢，我們來一起看一看：

1. 258:      int value = calculate<5>::process();  
2. 004013D8   call        @ILT+45(calculate<5>::process) (00401032)  
3. 004013DD   mov         dword ptr [ebp-4],eax  
4. 259:      return;  
5. 260:  }  

    上面就是調用引申的彙編的代碼。彙編和一般的函數調用無異，我們可以跟進去看看：

1. 242:          return calculate<m-1>::process() + m;  
2. 00401F68   call        @ILT+40(calculate<4>::process) (0040102d)  
3. 00401F6D   add         eax,5  
4. 243:      }  

    上面的代碼省略了中間的跳轉。我們發現代碼繼續調用了calculate<4>的靜态處理函數。這種調用當然會一直持續下去。那什麼時候結 束呢？對。就是前面說過的calculate<1>的靜态函數，就是前面說的特化函數，我們可以一起看看：

1. 250:      static int process()  
2. 251:      {  
3. 00402090   push        ebp  
4. 00402091   mov         ebp,esp  
5. 00402093   sub         esp,40h  
6. 00402096   push        ebx  
7. 00402097   push        esi  
8. 00402098   push        edi  
9. 00402099   lea         edi,[ebp-40h]  
10. 0040209C   mov         ecx,10h  
11. 004020A1   mov         eax,0CCCCCCCCh  
12. 004020A6   rep stos    dword ptr [edi]  
13. 252:          return 0;  
14. 004020A8   xor         eax,eax  
15. 253:      }  
16. 004020AA   pop         edi  
17. 004020AB   pop         esi  
18. 004020AC   pop         ebx  
19. 004020AD   mov         esp,ebp  
20. 004020AF   pop         ebp  
21. 004020B0   ret  

    看的出來，這裡才是真正的遞歸出口，到了這裡之後，函數開始折返，這也就意外着我們的計算即将結束。所有的流程和遞歸非常相似。是以遞歸函數和模闆遞歸的差別就是一點：遞歸函數是在代碼執行的時候完成的，模闆遞歸是在編譯的時候完成的。

思考題：

    自己編寫一個階乘的函數？嘗試一下是否可以轉變成遞歸函數？是否可以用模闆類遞歸得到呢？

【預告： 下面一片部落格介紹泛型函數處理】