遞歸調(diào)用的理解

2019-11-11 02:32:32

字體：大中小

供稿：網(wǎng)友

關(guān)于遞歸調(diào)用的理解問(wèn)題

前幾天做題的時(shí)候，發(fā)現(xiàn)《數(shù)據(jù)結(jié)構(gòu)高分筆記》第一章有這樣一個(gè)思考題，對(duì)理解遞歸調(diào)用幫助很大，題目如下：

題目：逆序輸出單鏈表的數(shù)據(jù)域，要求指針l指向鏈表首元結(jié)點(diǎn)，且只用l一個(gè)指針（一）分析：在單鏈表的情況下，要逆序輸出結(jié)點(diǎn)數(shù)據(jù)只用一個(gè)指針，除了用遞歸調(diào)用，好象沒(méi)有別的方法了。關(guān)鍵在于，如何設(shè)計(jì)遞歸調(diào)用？遞歸調(diào)用屬于分治法的一種思想，一個(gè)包含直接或者間接調(diào)用自身函數(shù)的語(yǔ)句的函數(shù)被稱為遞歸函數(shù)，但不是所有的調(diào)用自身都是遞歸，必須滿足以下條件：（1）在每一次調(diào)用自身時(shí)，必須是（在某種意義上）更接近于解；（2）必須有一個(gè)終止處理或者計(jì)算的準(zhǔn)則；設(shè)計(jì)的算法如下：————————————————————————————————————void reversePRint(LNode *l) //逆序輸出鏈表{if (l->next!= NULL){reversePrint(l->next);}cout << l->data<<" -- ";}———————————————————————————————————— 我們假設(shè)從首元結(jié)點(diǎn)到尾元結(jié)點(diǎn)共有9個(gè)結(jié)點(diǎn)，指針l指向首元結(jié)點(diǎn)，當(dāng)執(zhí)行到if語(yǔ)句時(shí)，很明顯” l->next!= NULL “成立，于是執(zhí)行“ reversePrint(l->next); ”進(jìn)入遞歸第二層，第二層循環(huán)執(zhí)行到if語(yǔ)句后同樣” l->next!= NULL “成立，于是進(jìn)入到遞歸第三層……值得說(shuō)明的是“ reversePrint(l->next); ”語(yǔ)句中，( )中必須寫成”( l->next )“，如果寫成(l)，便會(huì)進(jìn)入死循環(huán)，違背了上面條件（1）。而” l->next!= NULL “就是終止處理的準(zhǔn)則，也就是上面的條件（2）；當(dāng)進(jìn)入遞歸第九層以后，” l->next!= NULL “不成立，于是直接執(zhí)行" cout << l->data<<" -- "; "輸出結(jié)點(diǎn)9的數(shù)據(jù)，第九層遞歸執(zhí)行結(jié)束。但第九層遞歸執(zhí)行結(jié)束以后，第八層遞歸if語(yǔ)句執(zhí)行完畢，也進(jìn)入" cout << l->data<<" -- "; "語(yǔ)句輸出結(jié)點(diǎn)9的數(shù)據(jù)域，第八層遞歸執(zhí)行結(jié)束。以此類推，7、6、5、4、3、2、1依次執(zhí)行" cout << l->data<<" -- "; "語(yǔ)句，于是整個(gè)鏈表就被逆序輸出，而且從頭到尾l指針?biāo)傅氖冀K是首元結(jié)點(diǎn)（每一層的l可以看成每一層自己定義的指針，只不過(guò)名字相同，這點(diǎn)很重要）。因此，使用指針l，如果用for循環(huán)輸出則為正序，使用遞歸就可以達(dá)到逆序輸出的目的。另外值得一提的是" cout << l->data<<" -- "; "語(yǔ)句的位置因該放在函數(shù)哪里，也是一個(gè)值得深思的問(wèn)題。（二）關(guān)于遞歸調(diào)用的時(shí)間復(fù)雜度問(wèn)題如上九個(gè)結(jié)點(diǎn)，九層循環(huán)的時(shí)間復(fù)雜度為9，也就是說(shuō)這個(gè)算法時(shí)間復(fù)雜度為O(n)。初學(xué)者可能會(huì)懷疑時(shí)間復(fù)雜度為n次方，但是仔細(xì)比較就會(huì)發(fā)現(xiàn)，遞歸和循環(huán)的時(shí)間復(fù)雜度很類似。遞歸九層逆序輸出，時(shí)間復(fù)雜度為9；for(i=1;i<=9;i++){……}循環(huán)順序輸出9次，時(shí)間復(fù)雜度也是9。因此，靈活的使用遞歸和循環(huán)，可以解決線性表的各種順序以及逆序問(wèn)題！完整的代碼如下（VS2013編譯環(huán)境）：————————————————————————————————————// 逆序打印單鏈表的數(shù)據(jù) 指針l指向鏈表開(kāi)始要求只用l一個(gè)指針/*分析: 采用遞歸 printNode {if(l->next!=NULL)printNode(l->next);cout<<l->data;} 很神奇的想法！對(duì)理解遞歸有很大幫助！！！*/#include "stdafx.h"#include <iostream>#include "stdlib.h"using namespace std;static int length = 9;typedef struct LNode{ //結(jié)點(diǎn)的定義int data;struct LNode *next;}LNode;LNode *createLink( )//創(chuàng)立鏈表 {//創(chuàng)立頭結(jié)點(diǎn)LNode *head;head = (LNode *)malloc(sizeof(LNode));head->data = 0; head->next = NULL;//創(chuàng)立剩下的結(jié)點(diǎn)LNode *newNode, *p = head;for (int i = 1; i <= length; i++) {newNode = (LNode *)malloc(sizeof(LNode));newNode->data = i; newNode->next = NULL;p->next = newNode;p = p->next;}return head;}void printLink(LNode *head)//輸出鏈表 {cout << "當(dāng)前鏈表為：";LNode *temp = head->next;do{cout << temp->data << " -- ";temp = temp->next;} while (temp->next!=NULL);cout << temp->data;cout << endl;}void reversePrint(LNode *l) //逆序輸出鏈表{if (l->next!= NULL){reversePrint(l->next);}cout << l->data<<" -- ";}int _tmain(int argc, _TCHAR* argv[]){LNode *head = createLink();printLink(head);cout << "逆序鏈表為：";reversePrint(head->next); cout << endl;return 0;}————————————————————————————————————

輸出結(jié)果如下：