面試題目之逆向輸出鏈表
逆向輸出一個鏈表，不使用循環。
解決如下
2 {
3 if (head->next!=NULL)
4 {
5 reverseprint(head->next);
6 }
7 cout<<head->val<<endl;
8 }
9
這個題目用常規方法來做，比較繁瑣，因為鏈表是沒有前向指針的，我們即使遍歷到鏈表的尾部，也無法直接得到其前一個節點。所以必須要使用一個結構將前面的節點保存起來，然后輸出。所以這道題目使用遞歸還是很巧妙的。
遞歸要注意的就是這些語句前后放置的順序，否則就得不到想要的結果了。汗，添上這句話是因為我就寫錯了，后來才改正好。
其實遞歸就是利用C的函數調用規則，C在函數調用的時候，會將參數放入棧中，每調用一次函數，就會在棧中深入一層，當這個函數調用結束后，就會發生退棧操作，再執行下面的語句。遞歸就是函數自身調用自身，當然，在調用自身的時候，其參數和前提條件會發生相應的變化，從而使得不會產生無窮遞歸的情況。
如果你在編寫遞歸程序時沒有小心處理，填錯參數或者考慮沒有詳細的話，那有可能整個程序會異常終止，有時會報出內存訪問違例的錯誤，但是有時什么都不會報，直接什么都不輸出，此時你進入debug，可以看到一般都是發生了stack overflow的錯誤。因為C的函數棧空間是有限的，當遞歸的次數過多時，棧中容納不下這么多的內容，就會產生棧溢出錯誤。C中的棧的大小可以由程序員在編程的時候在編譯器中指定，默認有一個值，似乎是1M。要注意的是，這里的棧溢出和一般漏洞攻擊中提到的棧溢出不能算是一個概念。那里的棧溢出是利用一般是早期的字符串操作函數對字符參數不做安全性檢查，而構造一些特殊的字符，用來將下次函數調用的保存地址修改至自己函數地址，而達到執行自己代碼的目的。這里就不詳細展開，只是提到一下。
對于遞歸，主要有兩個問題，一個是遞歸算法一般來說，會出現重復性運算比較多，從而在運算效率上不是很高。（當然，這個也要看具體情況，可以看斐波那契數列的運算，用遞歸來計算斐波那契數列就會比較慢），同時，由于遞歸調用會用到函數調用，所以會有函數調用的開銷，函數調用會涉及到EBP，ESP等的入棧出棧操作，而自己直接使用棧則不會有這些開銷，但是自己申請的棧如果在堆區的話，堆區的訪問操作似乎比較慢一些。一般還是在棧區來申請一個數組來做，這樣基本就是指針的移動操作，比較快；第二個就是其對棧的占用問題，這個在PC機上體現不是很明顯，但是在嵌入式系統中，這個問題就比較嚴重，因為嵌入式系統本身的內存就不是很多，而分給棧的部分就更加的少，所以一般你看嵌入式開發公司的編程規范中，一般都會提到不要在其中使用遞歸。當然，節省內存是嵌入式系統一向的原則了。這里就還有一點，因為你不用遞歸來做，一般還是在棧上分配一塊內存來操作，這樣的話，如果內存分配過多，就一下子棧溢出了，所以一般內存分配比較多的，還是在堆上進行分配。
以上面這個逆向輸出鏈表為例，當遍歷到第一個節點時，如果沒有到鏈表尾部，則進入遞歸的函數調用，參數為下一個節點，此時就是遞歸的開始，此時函數調用不會結束，而是判斷是否到了鏈表尾部，沒有到則再次進入函數，如此反復，直到最后的一個節點，到達這個節點，就判斷到是到了尾部，此時不會進入判斷，而是執行cout輸出，此時就達到我們的逆向輸出目的，第一個輸出的是最后的一個節點；而其他節點呢，不是如我們所想的值啊什么的都存在棧中，而是前一個函數調用沒有結束，是前面的函數調用存在在棧中，當尾部節點輸出完畢后，該函數調用即會退出。而函數的退出點在reverseprint函數中第5行的后面，所以接著就會執行cout輸出，而輸出時的head值為前一個節點的值，所以輸出前一個節點的值，一直到最后第一個節點的值。
到cout語句輸出第一個節點值之后，在棧中已經沒有對reverseprint函數的調用了，此時整個遞歸調用結束。
【變體】
這個問題的擴展變體還有
1. 逆向輸出字符串
2. 定義一個函數求字符串的長度，要求該函數體內不能聲明任何變量
這里第一條根據上面一樣的道理，很快寫出來，但是要注意字符串，也就是char指針的問題
我第一次寫出的錯誤代碼如下
2 {
3 if (str!='\0')
4 {
5 reverseprintstr(str+1);
6 }
7 printf("%c",str);
8 }
修改之后，將最后的’\0’也一起輸出了
2 {
3 if (*str!='\0')
4 {
5 reverseprintstr(str+1);
6 }
7 printf("%c",*str);
8 }
9
最后的正確輸出代碼
2 {
3 if (*str!='\0')
4 {
5 reverseprintstr(str+1);
6 printf("%c",*str);
7 }
8 }
9
10 int main()
11 {
12 char str[]="hello world.";
13 reverseprintstr(str);
14 }
15
題2求字符串長度
2 {
3 if (*str=='\0')
4 {
5 return 0;
6 }
7 return mystrlen(str+1)+1;
8 }
9
10 int main()
11 {
12 char str[]="hello";
13 cout<<mystrlen(str)<<endl;
14 }
參考：http://bbs.tech.ccidnet.com/read.php?tid=681721
簡單的遞歸求解還有
用遞歸輸出乘法表，也就一起列在這里了
2 {
3 cout<<val1<<'*'<<val2<<'='<<val1*val2<<' ';
4 }
5
6 void fun(int val)
7 {
8 if(val==1)
9 output(val,val);
10 else
11 {
12 fun(val-1);
13 for(int i=1;i<=val;++i)
14 output(i,val);
15 }
16 cout<<endl;
17 }
18
19 void main()
20 {
21 int i;
22 cin>>i;
23 fun(i);
24 }
25
參考：http://topic.csdn.net/t/20020226/20/543919.html
上面的遞歸還是比較簡單的，如果在遞歸中再加上循環，在循環內進行遞歸，同時還有一些回溯的話，就比較復雜了，一般面試中比較復雜一些的遞歸題大概就是這個難度。
下面這段時間主要就是研究遞歸，將一些遞歸的題目列出來，并試著解決。大家有好的題目，也可以留言給我，多謝多謝。
留言列表
