本文從遞歸函數(shù)參數(shù)的角度來分析，遞歸函數(shù)調(diào)用時(shí)遞歸工作棧中工作記錄減肥的可能性。
用最簡單的求階層函數(shù)來舉例：
n! = n*(n-1)*(n-2)***2*1
常見的遞歸實(shí)現(xiàn)如下：
int fun(int n)
{
if( n<=1 ) return 1;
return n*fun(n-1);
}
不用多說，這個(gè)實(shí)現(xiàn)下每次遞歸調(diào)用都會(huì)在當(dāng)前層的工作記錄中分配一個(gè)4字節(jié)（IBM兼容機(jī)）的空間來存放n的值。若棧的深度為DEPTH，那么一共需要DEPTH×4個(gè)字節(jié)存放參數(shù)。
那么能不能避免這些存儲(chǔ)空間呢，我們來看看引用的情況：
int fun(int &n)
{
if( n<=1 ) return 1;
return n*fun(n-1);
}
這段代碼編譯不能通過，原因是n-1只是一個(gè)右值。這里簡單介紹一下c＋＋中的無名對(duì)象（變量）。c＋＋中的無名對(duì)象與const常量有些相似，他們都只能做右值而不能做左值，區(qū)別是const常量是有地址的可以取地址，而無名對(duì)象一般是不可以的。這里n－1有點(diǎn)無名對(duì)象的味道，因?yàn)閒un要求一個(gè)變量引用。由于n－1是右值，所以把參數(shù)類型改成int fun(const int & n)就可以了。
int fun(const int &n)
{
if( n<=1 ) return 1;
return n*fun(n-1);
}
現(xiàn)在運(yùn)行通過了，但是?？臻g需求仍然沒有減少，因?yàn)橐玫氖菬o名對(duì)象，無名對(duì)象只是寄存器中的一個(gè)值，是沒有RAM地址的。所以每遞歸調(diào)用一次，就會(huì)在工作記錄中分配空間來存放n－1，實(shí)際效果相當(dāng)于const int n = n-1;
那么換個(gè)思路。以上程序之所以如此是因?yàn)閭鹘o遞歸函數(shù)的不是n本身，現(xiàn)設(shè)計(jì)如下：
int fun(const int & n)
{
cout<<(long)&n<<endl;
if( n<=1 ) return 1;
--n;
return (n+1)*fun(n);
}
這個(gè)程序運(yùn)行正確而且所有的n確實(shí)是最外面的那個(gè)n的引用（打印的地址均一致）。有些人會(huì)懷疑這個(gè)程序不能正確的求出n!。想想也對(duì)，當(dāng)遞歸不斷深入到最里層的時(shí)候n＝1，遞歸回退的時(shí)候n仍然還是1，那結(jié)果不就成了1×2×2×2××××2了么？？您可以試試看，結(jié)果可能出乎您的預(yù)料：計(jì)算出的確實(shí)是 n! 原因如下：
每調(diào)用一層時(shí)先計(jì)算n+1，n＋1的結(jié)果保存在register中，進(jìn)入下一層遞歸前編譯器會(huì)把適當(dāng)?shù)膔egister的值壓棧以便日后恢復(fù)，這里某個(gè)寄存器就存放著運(yùn)算的中間結(jié)果n+1。日后返回該層時(shí)雖然此時(shí)n確實(shí)是1，但是n＋1的結(jié)果已經(jīng)計(jì)算過，所以只是從棧頂取出n+1而非重新計(jì)算。作為思考，您可以試試看將(n+1)*fun(n)改成fun(n)*(n+1)，它將得出錯(cuò)誤的結(jié)果。
看來，遞歸調(diào)用函數(shù)使用引用參數(shù)和普通使用引用參數(shù)的非遞歸調(diào)用函數(shù)是有區(qū)別的：并不是使用了引用參數(shù)后就一定能夠節(jié)省棧的空間，這取決于具體的遞歸函數(shù)（復(fù)雜。。。^_^）
當(dāng)然，在遞歸函數(shù)中使用引用參數(shù)還有一種目的，當(dāng)然是為了改變實(shí)參的數(shù)值羅。對(duì)于非內(nèi)部類型的對(duì)象而言，使用引用往往可以既節(jié)省空間又同時(shí)可以修改實(shí)參的值，這里就不再舉例了。
