【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：feixiaoxing @163.com】
遞歸，相信有過基本C語言經驗的朋友都明白，就是函數自己調用自己。所以，本質上說，它和普通的函數調用沒有什麼區別。今天之所以會把模板類和遞歸聯系在一起，是因為我們可以用遞歸的方法實現模板的遞歸。閒話不多說，我們先從一個統計函數開始說起。
int process(int m)
{
int index = 0;
int count = 0;
assert(m >= 0);
for (; index <=m; index++){
count += index;
}
return count;
}
int process(int m)
{
int index = 0;
int count = 0;
assert(m >= 0);
for (; index <=m; index++){
count += index;
}
return count;
}
上面的代碼不太難。大家可以看一下，其實就是一個和計算函數，它計算從0~m遞增的總和是多少。那麼這樣的一段代碼，用遞歸應該怎麼寫呢？大家可以自己試一下。下面的代碼是我自己的一個方案，供大家參考。
int process(int m)
{
assert(m >= 0);
if(m == 0)
return 0;
else
return process(m -1) + m;
}
int process(int m)
{
assert(m >= 0);
if(m == 0)
return 0;
else
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）的數值。這就是遞歸處理的全過程。
那麼，這和模板類有什麼關系，我們可以看看下面這個范例：
template<int m>
class calculate
{
public:
static int process()
{
return calculate<m-1>::process() + m;
}
};
template<>
class calculate<0>
{
public:
static int process()
{
return 0;
}
};
template<int m>
class calculate
{
public:
static int process()
{
return calculate<m-1>::process() + m;
}
};
template<>
class calculate<0>
{
public:
static int process()
{
return 0;
}
};
上面這段代碼非常有意思。我們發現模板的數據類型不再是int、double或者是自己定義的數據類型，而是一個一個具體的數字。但是每一種數字也代表了一種類型，所以說，calculate<5>和calculate<4>就是兩種不同的類。除此之外，我們還是用到了靜態處理函數。但是這裡的靜態函數有點特別，我們發現靜態函數process需要調用另外一個類的靜態函數，也就是calculate<m-1>的靜態函數才能獲得結果。所以為了獲得結果，我們需要創建很多的類和很多的靜態函數。那麼，類什麼時候結束呢？我們看到了calculate下面還有一個類，那就是calculate的特化模板，也就是說那m=0的時候，並不再繼續向下處理了，計算開始回歸。那麼這個類怎麼應用呢，我們來一起看一看：
258: int value = calculate<5>::process();
004013D8 call @ILT+45(calculate<5>::process) (00401032)
004013DD mov dword ptr [ebp-4],eax
259: return;
260: }
258: int value = calculate<5>::process();
004013D8 call @ILT+45(calculate<5>::process) (00401032)
004013DD mov dword ptr [ebp-4],eax
259: return;
260: }
上面就是調用引申的匯編的代碼。匯編和一般的函數調用無異，我們可以跟進去看看：
242: return calculate<m-1>::process() + m;
00401F68 call @ILT+40(calculate<4>::process) (0040102d)
00401F6D add eax,5
243: }
242: return calculate<m-1>::process() + m;
00401F68 call @ILT+40(calculate<4>::process) (0040102d)
00401F6D add eax,5
243: }
上面的代碼省略了中間的跳轉。我們發現代碼繼續調用了calculate<4>的靜態處理函數。這種調用當然會一直持續下去。那什麼時候結束呢？對。就是前面說過的calculate<1>的靜態函數，就是前面說的特化函數，我們可以一起看看：
250: static int process()
251: {
00402090 push ebp
00402091 mov ebp,esp
00402093 sub esp,40h
00402096 push ebx
00402097 push esi
00402098 push edi
00402099 lea edi,[ebp-40h]
0040209C mov ecx,10h
004020A1 mov eax,0CCCCCCCCh
004020A6 rep stos dword ptr [edi]
252: return 0;
004020A8 xor eax,eax
253: }
004020AA pop edi
004020AB pop esi
004020AC pop ebx
004020AD mov esp,ebp
004020AF pop ebp
004020B0 ret
250: static int process()
251: {
00402090 push ebp
00402091 mov ebp,esp
00402093 sub esp,40h
00402096 push ebx
00402097 push esi
00402098 push edi
00402099 lea edi,[ebp-40h]
0040209C mov ecx,10h
004020A1 mov eax,0CCCCCCCCh
004020A6 rep stos dword ptr [edi]
252: return 0;
004020A8 xor eax,eax
253: }
004020AA pop edi
004020AB pop esi
004020AC pop ebx
004020AD mov esp,ebp
004020AF pop ebp
004020B0 ret
看的出來，這裡才是真正的遞歸出口，到了這裡之後，函數開始折返，這也就意外著我們的計算即將結束。所有的流程和遞歸非常相似。所以遞歸函數和模板遞歸的區別就是一點：遞歸函數是在代碼執行的時候完成的，模板遞歸是在編譯的時候完成的。
思考題：
自己編寫一個階乘的函數？嘗試一下是否可以轉變成遞歸函數？是否可以用模板類遞歸得到呢？
