C語言遞回函數

遞回（recursive）函數是“自己呼叫自己”的函數，無論是採用直接或間接呼叫方式。間接遞回意味著函數呼叫另一個函數（然後可能又呼叫第三個函數等），最後又呼叫第一個函數。因為函數不可以一直不停地呼叫自己，所以遞回函數一定具備結束條件。

在例 1 中，遞回函數 binarySearch（）實現二元搜尋演算法，在排序好的陣列中找到特定元素。首先，該函數根據搜尋條件比較陣列最中間的元素。如果相同，就返問該元素的指標，表示找到了；如果不相同，該函數會呼叫自己，在可能存在滿足搜尋條件的一半陣列中搜尋，一直遞回地進行下去，指導找到滿足搜尋條件的元素。如果剩下陣列的長度為 0，則表示找不到，那麼遞回就會結束。

【例1】函數 binarySearch（）

// 函數 binarySearch() 在排序好的陣列中搜尋
// 引數：需要搜尋的元素值；待搜尋的long型別陣列；陣列的長度
// 返回值：指向滿足搜尋條件的元素的指標，或者為NULL，如果陣列中沒有元素滿足搜尋條件。
long *binarySearch( long val, long array[ ], int n )
{
  int m = n/2;
  if ( n <= 0 )               return NULL;
  if ( val == array[m] ) return array + m;
  if ( val < array[m] )  return binarySearch( val, array, m );
  else                           return binarySearch( val, array+m+1, n-m-1 );
}

對於有 n 個元素的陣列來說，二元搜尋演算法進行最多 1+log2（n）次比較。如果有一百萬個元素，最多比較 20 次，也就是最多 20  次遞回執行函數  binarysearch（）。

遞回函數基於了這樣一個事實：每次呼叫函數時，都會重新建立動態變數。這些變數，以及返回時需要的呼叫者地址，都儲存在棧中，每次函數遞迴都會造成棧上新增一塊資料。程式設計師要確保棧的空間夠大，足以容納遞回的中間處理過程。不過例 1 中的函數 binarySearch（）對於棧空間的要求並不大。

遞回函數是採用邏輯方式來實現自然遞回規律的演算法，例如二元搜尋技術，或者樹狀結構導航（navigation）。

然而，即使遞回函數可以對某些問題提供優雅而緊湊的解決方案，但採用簡單回圈的解決方案也常常是可行的。例如，可以用迴圈改寫例 1 的二元搜尋演算法，而不使用遞回函數呼叫。在這種情況下，採用迴圈的解決方案通常會比採用遞迴的解決方案執行效率更高。