原文地址：http://www.cnblogs.com/coderkian/p/3758068.html
遞歸函數(shù)具有很好的可讀性和可維護(hù)性郊供，但是大部分情況下程序效率不如非遞歸函數(shù)，所以在程序設(shè)計(jì)中一般喜歡先用遞歸解決問題，在保證方法正確的前提下再轉(zhuǎn)換為非遞歸函數(shù)以提高效率科展。
函數(shù)調(diào)用時(shí)，需要在棧中分配新的幀述呐，將返回地址菇晃，調(diào)用參數(shù)和局部變量入棧。所以遞歸調(diào)用越深呆万，占用的椛淘矗空間越多。如果層數(shù)過深谋减，肯定會(huì)導(dǎo)致棧溢出牡彻，這也是消除遞歸的必要性之一。遞歸函數(shù)又可以分為尾遞歸和非尾遞歸函數(shù)出爹，前者往往具有很好的優(yōu)化效率庄吼，下面我們分別加以討論缎除。
尾遞歸函數(shù)
尾遞歸函數(shù)是指函數(shù)的最后一個(gè)動(dòng)作是調(diào)用函數(shù)本身的遞歸函數(shù)，是遞歸的一種特殊情形总寻。尾遞歸具有兩個(gè)主要的特征：
- 調(diào)用自身函數(shù)(Self-called)磺浙；
- 計(jì)算僅占用常量椝跬幔空間(Stack Space)萨咕。
為什么尾遞歸可以做到常量椀铮空間，我們用著名的fibonacci數(shù)列作為例子來說明殊轴。
fibonacci數(shù)列實(shí)現(xiàn)方法一般是這樣的衰倦，
int FibonacciRecur(int n) {
if (0==n) return 0;
if (1==n) return 1;
return FibonacciRecur(n-1)+FibonacciRecur(n-2);
}
不過需要注意的是這種實(shí)現(xiàn)方法并不是尾遞歸袒炉，因?yàn)槲策f歸的最后一個(gè)動(dòng)作必須是調(diào)用自身旁理，這里最后的動(dòng)作是加法運(yùn)算，所以我們要修改一下我磁，
int FibonacciTailRecur(int n, int acc1, int acc2) {
if (0==n) return acc1;
return FibonacciTailRecur(n-1, acc2, acc1+acc2);
}
好了孽文，現(xiàn)在符合尾遞歸的定義了，用gcc分別加-O和-O2選項(xiàng)編譯夺艰，下面是部分匯編代碼芋哭，
- O2匯編代碼
FibonacciTailRecur:
.LFB12:
testl %edi, %edi
movl %esi, %eax
movl %edx, %esi
je .L4
.p2align 4,,7
.L7:
leal (%rax,%rsi), %edx
decl %edi
movl %esi, %eax
testl %edi, %edi
movl %edx, %esi
jne .L7 // use jne .L4:
rep ; ret
- O匯編代碼
FibonacciTailRecur:
.LFB2:
pushq %rbp
.LCFI0:
movq %rsp, %rbp
.LCFI1:
subq $16, %rsp
.LCFI2:
movl %edi, -4(%rbp)
movl %esi, -8(%rbp)
movl %edx, -12(%rbp)
cmpl $0, -4(%rbp)
jne .L2
movl -8(%rbp), %eax
movl %eax, -16(%rbp)
jmp .L1
.L2:
movl -12(%rbp), %eax
movl -8(%rbp), %edx
addl %eax, %edx
movl -12(%rbp), %esi
movl -4(%rbp), %edi
decl %edi
call FibonacciTailRecur //use call
movl %eax, -16(%rbp)
.L1:
movl -16(%rbp), %eax
leave
ret
可以看到-O2時(shí)用了jne命令，每次調(diào)用下層遞歸并沒有申請(qǐng)新的椨舾保空間减牺，而是更新當(dāng)前幀的局部數(shù)據(jù)，重復(fù)使用當(dāng)前幀存谎，所以不管有多少層尾遞歸調(diào)用都不會(huì)棧溢出拔疚，這也是使用尾遞歸的意義所在。
而-O使用的是call命令既荚，這會(huì)申請(qǐng)新的椫墒В空間，也就是說gcc默認(rèn)狀態(tài)下并沒有優(yōu)化尾遞歸恰聘，這么做的一個(gè)主要原因是有時(shí)候我們需要保留幀信息用于調(diào)試句各，而加-O2優(yōu)化后，不管多少層尾遞歸調(diào)用晴叨，使用的都是第一層幀凿宾，是得不到當(dāng)前幀的信息的，大家可以用gdb調(diào)試下就知道了兼蕊。
除了尾遞歸初厚，F(xiàn)ibonacci數(shù)列很容易推導(dǎo)出循環(huán)實(shí)現(xiàn)方式，
int fibonacciNonRecur(int n) {
int acc1 = 0, acc2 = 1;
for(int i=0; i<n; i++){
int t = acc1;
acc1 = acc2;
acc2 += t;
}
return acc1;
}
在我的機(jī)器上遍略，全部加-O2選項(xiàng)優(yōu)化編譯惧所，運(yùn)行時(shí)間如下（單位微秒）
| n | fibonacciNonRecur | FibonacciTailRecur | FibonacciRecur |
|---|---|---|---|
| 20 | 1 | 1 | 123 |
| 30 | 1 | 1 | 14144 |
將fibonacci函數(shù)的迭代骤坐，尾遞歸和遞歸函數(shù)性能比較，可以發(fā)現(xiàn)迭代和尾遞歸時(shí)間幾乎一致下愈，n的大小對(duì)迭代和尾遞歸運(yùn)行時(shí)間影響很小纽绍，因?yàn)橹皇嵌鄨?zhí)行O（n）條機(jī)器指令而已。但是n對(duì)遞歸函數(shù)影響非常大势似，這是由于遞歸需要頻繁分配回收棸柘模空間所致。正是由于尾遞歸的高效率履因，在一些語言如lua中就明確建議使用尾遞歸（參照《lua程序設(shè)計(jì)第二版》第6章）障簿。
非尾遞歸函數(shù)
編譯器無法自動(dòng)優(yōu)化一般的遞歸函數(shù)，不過通過模擬遞歸函數(shù)的過程栅迄，我們可以借助于棧將任何遞歸函數(shù)轉(zhuǎn)換為迭代函數(shù)站故。直觀點(diǎn)，遞歸的過程其實(shí)是編譯器幫我們處理了壓棧和出棧的操作毅舆，轉(zhuǎn)換為迭代函數(shù)就需要手動(dòng)地處理壓棧和出棧西篓。
下面我們以經(jīng)典的快速排序?yàn)槔印?/p>
int partition(int *array, int low, int high) {
int val = array[low];
while(low < high) {
while(low<high && array[high]>=val) --high;
swap(&array[low], &array[high]);
while(low<high && array[low]<=val) ++low;
swap(&array[low], &array[high]);
}
return low;
}
void Quicksort(int *array, int b, int e) {
if (b >= e) return;
int p = partition(array, b, e);
Quicksort(array, b, p-1);
Quicksort(array, p+1, e);
}
其實(shí)不難看出快速排序的遞歸算法就是一個(gè)二叉樹的先序遍歷過程，先處理當(dāng)前根節(jié)點(diǎn)憋活，然后依次處理左子樹和右子樹岂津。將快速排序遞歸算法轉(zhuǎn)換為非遞歸相當(dāng)于將二叉樹先序遍歷遞歸算法轉(zhuǎn)為非遞歸算法。
二叉樹先序遍歷遞歸算法偽碼
void PreorderRecursive(Bitree root){
if (root) {
visit(root);
PreorderRecursive(root->lchild);
PreorderRecursive(root->rchild);
}
}
二叉樹先序遍歷非遞歸偽碼
void PreorderNonRecursive(Bitree root){
stack stk;
stk.push(root);
while(!stk.empty()){
p = stk.top();
visit(p);
stk.pop();
if(p.rchild) stk.push(stk.rchild);
if(p.lchild) stk.push(stk.lchild);
}
}
每次處理完當(dāng)前節(jié)點(diǎn)后將右子樹和左子樹分別入棧悦即，類似地吮成，我們也很容易得到快速排序的非遞歸算法實(shí)現(xiàn)。partition將數(shù)組分為左右兩部分辜梳，相當(dāng)與處理當(dāng)前節(jié)點(diǎn)粱甫，接下來要做的就是將左右子樹入棧，那么左右子樹需要保存什么信息呢冗美？這個(gè)是處理非遞歸函數(shù)的關(guān)鍵魔种，因?yàn)楸徽{(diào)用函數(shù)信息需要壓入棧中》弁荩快速排序只需要保存子數(shù)組的邊界即可节预。
void QuicksortNonRecur(int *array, int b, int e) {
if (b >= e) return;
std::stack< std::pair<int, int> > stk;
stk.push(std::make_pair(b, e));
while(!stk.empty()) {
std::pair<int, int> pair = stk.top();
stk.pop();
if(pair.first >= pair.second) continue;
int p = partition(array, pair.first, pair.second);
if(p < pair.second) stk.push(std::make_pair(p+1, e));
if(p > pair.first) stk.push(std::make_pair(b, p-1));
}
}
總結(jié)
雖然將遞歸函數(shù)轉(zhuǎn)換為迭代函數(shù)可以提高程序效率，但是轉(zhuǎn)換后的迭代函數(shù)往往可讀性差属韧，難以理解安拟，不易維護(hù)。所以只有在特殊情況下宵喂，比如對(duì)椏飞猓空間有嚴(yán)格要求的嵌入式系統(tǒng)，才需要轉(zhuǎn)換遞歸函數(shù)。大部分情況下拙泽，遞歸并不會(huì)成為系統(tǒng)的性能瓶頸淌山，一個(gè)代碼簡單易讀的遞歸函數(shù)常常比迭代函數(shù)更易維護(hù)。
Reference：
https://secweb.cs.odu.edu/~zeil/cs361/web/website/Lectures/recursionConversion/page/recursionConversion.html
http://en.wikipedia.org/wiki/Tail_Recursion
http://c2.com/cgi/wiki?TailRecursion
http://c2.com/cgi/wiki?RecursionVsLoop
