遞歸算法（Recursion method）是函數根據遞歸條件不斷調用自身并在一定條件下返回的方法，這樣的函數稱為遞歸函數。編譯器在函數調用時會維護一個内存棧，一次函數調用會生成一個函數棧幀，在棧幀中保存有返回地址址，一些寄存器的原始值和更新值、參數值、中間變量，這些值依次壓棧，并在函數返回時逆序依次彈出。遞歸函數的依次調用會依次建立棧幀，每個函數棧幀的參數（如果有）一般會形成一個叠代關系。而遞歸函數本身也可以在相互遞推、遞歸返回中形成一個叠代關系。

遞歸法也有分治法的思想，子問題之間是同類、縱向的關系。（枚舉法的子問題之間是橫向的關系）

一般來講，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進，當邊界條件滿足時，遞歸返回。在使用遞歸策略時，必須有一個明确的遞歸結束條件，稱為遞歸出口。

在計算機編程應用中，遞歸算法對解決大多數問題是十分有效的，它能夠使算法的描述變得簡潔而且易于理解。遞歸算法有如下3 個特點。

① 遞歸過程一般通過函數或子過程來實現。

② 遞歸算法在函數或子過程的内部，直接或者間接地調用自己的算法。

③ 遞歸算法實際上是把問題轉化為規模縮小了的同類問題的子問題，然後再遞歸調用函數或過程來表示問題的解。子函數相對于其遞歸函數，問題性質相同（解決問題的步驟），規模較小。

在使用遞歸算法時，應該注意如下4 點。

① 遞歸是在過程或函數中調用自身的過程。

② 在使用遞歸策略時，首先要确定遞歸表達式，然後必須有一個明确的遞歸結束條件，這稱為遞歸出口。

③ 遞歸算法通常顯得很簡潔，但是運行效率較低，所以一般不提倡用遞歸算法設計程序。

④ 在遞歸調用過程中，系統用棧來存儲每一層的返回點和局部量。如果遞歸次數過多，則容易造成棧溢出，所以一般不提倡用遞歸算法設計程序。

⑤ 理解遞歸首先要較深入理解編譯器調用函數、使用内存棧，壓參數、參數叠代、以及保存返回值或返回值地址到寄存器，彈棧，返回值或地址值的一整個流程。

⑥ 理解遞歸的另一個重點要理解函數遞歸了n次，這n份代碼的執行流程，在每份遞歸函數代碼中，以遞歸語句為基準，前面的語句由遞推階段執行，後面的語句在遞推返回階段執行（如果是尾遞歸，這部分沒有），遞歸語句本身作為函數調用和值返回（如果有的話）。

因為遞歸算法思想往往用函數的形式來體現，所以遞歸算法需要預先編寫功能函數。這些函數是獨立的功能，能夠實現解決某個問題的具體功能，當需要時直接調用這個函數即可。遞歸函數的一般格式：

if(邊界條件1成立) { 賦予邊界值1 } else if(邊界條件2成立) { 賦予邊界值2 } else { 調用遞歸表達式 }

遞歸應用的實例随處可見，如階乘、漢諾塔問題、斐波那契數列問題、快速排序、二分查找等。

對于尾遞歸（遞歸語句後還有代碼），如階乘，通常較容易轉化為循環來解決，非尾遞歸（遞歸語句後沒有代碼了），如漢諾塔問題，用循環解決往往較複雜，需要另外使用一個棧的數據結構。

二分查找問題可以用遞歸解決，代碼看起來很簡潔，也可以用循環解決，效率較高：

// 遞歸有自調用的問題，需要将start和end寫在參數列表中 // 來标記和動态變更搜索範圍的開始和結束 int bisoRecurs(int arr[], int findData, int start, int end) { if(arr==NULL || start>end) return -1; int mid = start (end-start)/2; if(arr[mid] == findData) return mid; else if(findData < arr[mid]) bisoRecurs(arr, findData, start, mid-1); // 參數叠代 end = mid-1且有壓棧 else bisoRecurs(arr, findData, mid 1, end); // 參數叠代 start = mid-1且有壓棧 }

遞歸算法的代碼之所以簡潔，是因為其複雜性由編譯器完成了，由編譯器自動維護的内存棧，并自動完成入棧和出棧的工作。

遞歸函數與其子函數兩者的性質完全相同，區别隻在于子函數的規模較小，所以是分治法的一種體現。且因上述的自動遞歸調用與返回，且在調用之間函數參數實現了叠代，所以其應用非常廣泛（C ｜18個使用遞歸的實例）。但其弊端也正在如此，函數的調用會帶來空間和時間效率方面的損耗。

在典型算法思想與應用2｜叠代法與近似求函數值和最大公約數問題一文中有提到用二分法和叠代法解決求平方根問題，自然用遞歸也行：

double squareRoot(double a, double x0) // 13 求平方根 { double ans; double x1=(x0 a/x0)/2; if(fabs(x1-x0)>1e-8) ans = squareRoot(a,x1); else ans=x1; return ans; }

仔細想了一下，說遞歸如果不貼一下漢諾塔問題的代碼，似乎不完整（因為此問題用循環寫需要棧來輔助，寫起來非常繁雜，而遞歸實現雖然其編譯器内部複雜，還有重複求值的問題，但代碼簡潔）：

void hanoi(int n, char from, char temp, char to) // 16 漢諾塔 { if (n==1) printf("%c→%c(1)\n",from,to); else { hanoi(n-1,from,to,temp); //将x上編号為1到n-1的圓盤移到y，z作輔助塔 printf("%c→%c\n",from,to); //将x上編号為n的圓盤移到z hanoi(n-1,temp,from,to); //将y上編号為1到n-1的圓盤移到z，y作輔助塔 } } void main16() { hanoi(3,'A','B','C'); cin.get(); } /* A→C(1) A→B C→B(1) A→C B→A(1) B→C A→C(1) */

附二分查找的遞歸與非遞歸實現

#include<iostream> // 二分查找的遞歸與非遞歸實現 using namespace std; // 分治法，可分，可合，子問題有獨立性 int bisoLoop(int arr[], int len, int findData) { if(arr==NULL || len <=0) return -1; int start = 0; int end = len-1; while(start<=end) { int mid = start (end-start)/2; if(arr[mid] == findData) return mid; else if(findData < arr[mid]) end = mid-1; else start = mid 1; } return -1; } // 遞歸有自調用的問題，需要将start和end寫在參數列表中 // 來标記和動态變更搜索範圍的開始和結束 int bisoRecurs(int arr[], int findData, int start, int end) { if(arr==NULL || start>end) return -1; int mid = start (end-start)/2; if(arr[mid] == findData) return mid; else if(findData < arr[mid]) bisoRecurs(arr, findData, start, mid-1); else bisoRecurs(arr, findData, mid 1, end); } void main() { int arr[] = {1,2,3,4,5,6,7,8}; int len = sizeof(arr)/sizeof(arr[0]); int index = bisoLoop(arr,len,6); int index2 = bisoRecurs(arr,6,0,len-1); cout<<index<<endl; cout<<index2<<endl; system("pause"); } /* 5 5 */

－End－

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!