用一隻海龜來引入「遞歸」,是有一些滑稽,但也沒有關係。可能你更喜歡的是海龜而不是無窮的遞歸調用,那遞歸長什麼樣呢?
各種表現,比如這些樣子:
從前有座山,山裡有座廟,廟裡有個老和尚,老和尚給小和尚講故事,講的是從前有座山。。。。
這些例子可以看到遞歸的影子,可以感受到遞歸的一個特點就是「嵌套」,一層套一層,層層新。正如我說的,一定要用自己的話突出重點地表達你的理解,不要完整或完善,那麼,遞歸是什麼?
遞歸就是調用自己,調用自己的就是遞歸,就這麼簡單。「自己」是什麼?「自己」是一個遞歸結構或演算法。
為什麼能夠調用自己?
之所以能調用自己,是因為子問題也能用原問題的解決辦法。遞歸的設計,就是把問題分解成更小的問題,而且更小的問題也能用原問題的解決辦法。在問題規模足夠小的時候,把它解決掉,再層層返回,層層組合。
如果非要說一個偉大的思想來突顯遞歸的nb,那就是以退為進,在遇到問題很複雜你解決不了的情況下,退一步,如果退一步還解決不了,就再退一步--沒有什麼問題是退一步解決不了的,如果有,那就退兩步。在退到足夠簡單的情況下,把它解決,再回歸。這個是不是很厲害?
當然你也可以用數學歸納法來考證遞歸的偉大,但我覺得大可不必,更多情況下,遞歸只是解決問題的小工具。
那麼,這個小工具怎麼用起來?走你!
使用遞歸時,有兩個要點可以考慮,一是如何調用自己,包括自己返回後怎麼處理,二是在什麼時候結束遞歸。
說多無謂,實戰出感悟。不考慮性能,看幾個問題的遞歸解決吧。
問題1:輸入數字n,列印出1到n的所有整數。
主體:要列印1到n,那先列印1到n-1,再列印一個n就可以了。這個就是主體,只考慮n跟n-1。 結束:在n為1時列印1,並結束遞歸。
主體:要列印1到n,那先列印1到n-1,再列印一個n就可以了。這個就是主體,只考慮n跟n-1。
代碼示例:
void pr(int n) { if (n == 1) { printf("1 "); return; } pr(n-1); printf("%d ", n); }
效果:
問題2:輸出「我當然知道 我知道 我知道 我知道 ...我是個sb 這件事 這件事...這件事」,輸入n來控制次數。
主體:把「我當然知道」放在遞歸函數外,因為它不符合同構的原則。先輸出「我知道」,再遞歸到下一層即可。 結束:在遞減到0時,結束遞歸。 收尾:在遞歸返回後,輸出「這件事」。
主體:把「我當然知道」放在遞歸函數外,因為它不符合同構的原則。先輸出「我知道」,再遞歸到下一層即可。
#include <stdio.h>
void pr(int n) { if (n == 0) { printf("[我是sb]"); return; } printf("我知道["); pr(n-1); printf("這件事]"); }
int main(int argc, char *argv[]) { printf("我當然知道{"); pr(10); printf("} "); return 0; }
問題3:求二叉樹的高度(最長路徑)。
主體:左子樹與右子樹的高度的最大值,加1就是當前樹的高度。 結束:沒有子樹了。
主體:左子樹與右子樹的高度的最大值,加1就是當前樹的高度。
int treeHeight(struct TreeNode* root) { if (!root) return 0; int left = treeHeight(root->left); int right = treeHeight(root->right); return MAX(left, right) + 1; }
問題4:求數組中的最大值與最小值。
演示代碼:
#include <iostream> using namespace std;
template<typename T> void max_min( T a[], int low, int high, T & max, T & min) { if ( low == high ) // 只有一個元素不再劃分 { max = min = a[low]; return; } else if ( low == high -1 ) // 只有兩上元素不再劃分 { if ( a[low] < a[high] ) { max = a[high]; min = a[low]; } else { max = a[low]; min = a[high]; } return; }
int mid = (low + high) / 2; T max_another; T min_another; max_min( a, low, mid, max, min ); max_min( a, mid+1, high, max_another, min_another );
if ( max < max_another ) max = max_another; if ( min > min_another ) min = min_another; }
int _tmain(int argc, _TCHAR* argv[]) { double a[5] = {23.23, 23.45, .3, -89.3, -2.1}; double max, min; max_min<double>( a, 0, 4, max, min ); cout << "max: " << max << " min: " << min << endl;
return 1; }
最後,再提一下遞歸的深度。
每次遞歸調用都意味著部分數值壓入棧中(比如系統維護的下壓棧),這是跟迭代的區別。在迭代中每次循環結束時所有局部變數都獲得釋放,而遞歸卻會不斷累計,所以使用遞歸演算法必須考慮它的深度,考慮是否會造成棧溢出,與及對效率造成的影響。
另外,每一次遞歸調用,問題的規模都應該有所減少,並最終達到終止條件的要求,從而結束遞歸調用。
至此,遞歸的入門介紹完畢了。
總結一下,本文介紹了遞歸的表現、遞歸的理解與設計,最後舉了幾個例子並用遞歸的思路來實現。遞歸是一個重要的思考問題的思路,希望能幫到你。
推薦閱讀: