前言：今天上網(wǎng)看帖子的時(shí)候，看到關(guān)于尾遞歸的應(yīng)用（http://bbs.csdn.net/topics/390215312），大腦中感覺(jué)這個(gè)詞好像在哪里見(jiàn)過(guò)，但是又想不起來(lái)具體是怎么回事。如是乎，在網(wǎng)上搜了一下，頓時(shí)豁然開(kāi)朗，知道尾遞歸是怎么回事了。下面就遞歸與尾遞歸進(jìn)行總結(jié)，以方便日后在工作中使用。

1、遞歸

　　關(guān)于遞歸的概念，我們都不陌生。簡(jiǎn)單的來(lái)說(shuō)遞歸就是一個(gè)函數(shù)直接或間接地調(diào)用自身，是為直接或間接遞歸。一般來(lái)說(shuō)，遞歸需要有邊界條件、遞歸前進(jìn)段和遞歸返回段。當(dāng)邊界條件不滿足時(shí)，遞歸前進(jìn)；當(dāng)邊界條件滿足時(shí)，遞歸返回。用遞歸需要注意以下兩點(diǎn)：(1) 遞歸就是在過(guò)程或函數(shù)里調(diào)用自身。(2) 在使用遞歸策略時(shí)，必須有一個(gè)明確的遞歸結(jié)束條件，稱為遞歸出口。

遞歸一般用于解決三類問(wèn)題： 　??(1)數(shù)據(jù)的定義是按遞歸定義的。（Fibonacci函數(shù)，n的階乘） 　 ?(2)問(wèn)題解法按遞歸實(shí)現(xiàn)。（回溯） 　 ?(3)數(shù)據(jù)的結(jié)構(gòu)形式是按遞歸定義的。（二叉樹(shù)的遍歷，圖的搜索） 遞歸的缺點(diǎn)： 遞歸解題相對(duì)常用的算法如普通循環(huán)等，運(yùn)行效率較低。因此，應(yīng)該盡量避免使用遞歸，除非沒(méi)有更好的算法或者某種特定情況，遞歸更為適合的時(shí)候。在遞歸調(diào)用的過(guò)程當(dāng)中系統(tǒng)為每一層的返回點(diǎn)、局部量等開(kāi)辟了棧來(lái)存儲(chǔ)，因此遞歸次數(shù)過(guò)多容易造成棧溢出。 用線性遞歸實(shí)現(xiàn)Fibonacci函數(shù)，程序如下所示： 1 int FibonacciRecursive(int n) 2 { 3 if( n < 2) 4 return n; 5 return (FibonacciRecursive(n-1)+FibonacciRecursive(n-2)); 6 }

遞歸寫(xiě)的代碼非常容易懂，完全是根據(jù)函數(shù)的條件進(jìn)行選擇計(jì)算機(jī)步驟。例如現(xiàn)在要計(jì)算n=5時(shí)的值，遞歸調(diào)用過(guò)程如下圖所示：

2、尾遞歸

　　顧名思義，尾遞歸就是從最后開(kāi)始計(jì)算, 每遞歸一次就算出相應(yīng)的結(jié)果, 也就是說(shuō), 函數(shù)調(diào)用出現(xiàn)在調(diào)用者函數(shù)的尾部, 因?yàn)槭俏膊? 所以根本沒(méi)有必要去保存任何局部變量. 直接讓被調(diào)用的函數(shù)返回時(shí)越過(guò)調(diào)用者, 返回到調(diào)用者的調(diào)用者去。尾遞歸就是把當(dāng)前的運(yùn)算結(jié)果（或路徑）放在參數(shù)里傳給下層函數(shù)，深層函數(shù)所面對(duì)的不是越來(lái)越簡(jiǎn)單的問(wèn)題，而是越來(lái)越復(fù)雜的問(wèn)題，因?yàn)閰?shù)里帶有前面若干步的運(yùn)算路徑。

　　尾遞歸是極其重要的，不用尾遞歸，函數(shù)的堆棧耗用難以估量，需要保存很多中間函數(shù)的堆棧。比如f(n,?sum)?=?f(n-1)?+?value(n)?+?sum;?會(huì)保存n個(gè)函數(shù)調(diào)用堆棧，而使用尾遞歸f(n,?sum)?=?f(n-1,?sum+value(n));?這樣則只保留后一個(gè)函數(shù)堆棧即可，之前的可優(yōu)化刪去。

　　采用尾遞歸實(shí)現(xiàn)Fibonacci函數(shù)，程序如下所示：

1 int FibonacciTailRecursive(int n,int ret1,int ret2) 2 { 3 if(n==0) 4 return ret1; 5 return FibonacciTailRecursive(n-1,ret2,ret1+ret2); 6 }

例如現(xiàn)在要計(jì)算n=5時(shí)的值，尾遞歸調(diào)用過(guò)程如下圖所示：

從圖可以看出，為遞歸不需要向上返回了，但是需要引入而外的兩個(gè)空間來(lái)保持當(dāng)前的結(jié)果。

　　為了更好的理解尾遞歸的應(yīng)用，寫(xiě)個(gè)程序進(jìn)行練習(xí)。采用直接遞歸和尾遞歸的方法求解單鏈表的長(zhǎng)度，C語(yǔ)言實(shí)現(xiàn)程序如下所示：

1 #include <stdio.h> 2 #include <stdlib.h> 3 4 typedef struct node 5 { 6 int data; 7 struct node* next; 8 }node,*linklist; 9 10 void InitLinklist(linklist* head) 11 { 12 if(*head != NULL) 13 free(*head); 14 *head = (node*)malloc(sizeof(node)); 15 (*head)->next = NULL; 16 } 17 18 void InsertNode(linklist* head,int d) 19 { 20 node* newNode = (node*)malloc(sizeof(node)); 21 newNode->data = d; 22 newNode->next = (*head)->next; 23 (*head)->next = newNode; 24 } 25 26 //直接遞歸求鏈表的長(zhǎng)度 27 int GetLengthRecursive(linklist head) 28 { 29 if(head->next == NULL) 30 return 0; 31 return (GetLengthRecursive(head->next) + 1); 32 } 33 //采用尾遞歸求鏈表的長(zhǎng)度，借助變量acc保存當(dāng)前鏈表的長(zhǎng)度，不斷的累加 34 int GetLengthTailRecursive(linklist head,int *acc) 35 { 36 if(head->next == NULL) 37 return *acc; 38 *acc = *acc+1; 39 return GetLengthTailRecursive(head->next,acc); 40 } 41 42 void PrintLinklist(linklist head) 43 { 44 node* pnode = head->next; 45 while(pnode) 46 { 47 printf("%d->",pnode->data); 48 pnode = pnode->next; 49 } 50 printf("->NULL\n"); 51 } 52 53 int main() 54 { 55 linklist head = NULL; 56 int len = 0; 57 InitLinklist(&head); 58 InsertNode(&head,10); 59 InsertNode(&head,21); 60 InsertNode(&head,14); 61 InsertNode(&head,19); 62 InsertNode(&head,132); 63 InsertNode(&head,192); 64 PrintLinklist(head); 65 printf("The length of linklist is: %d\n",GetLengthRecursive(head)); 66 GetLengthTailRecursive(head,&len); 67 printf("The length of linklist is: %d\n",len); 68 system("pause"); 69 }

程序測(cè)試結(jié)果如下圖所示：

總結(jié)

以上是生活随笔為你收集整理的递归与尾递归总结的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。