PHP - 遞迴函式

遞迴函式是指這樣一種函式，它會一直呼叫自身，直到滿足某個條件。在 PHP 中，可以定義遞迴函式。

• 當某個問題用自身來定義時，就會用到遞迴。

• 有時，使用迭代方法解決問題可能會很繁瑣。遞迴方法為看似複雜的問題提供了非常簡潔的解決方案。

• PHP 中的遞迴與 C 和 C++ 中的非常相似。

• 遞迴函式特別用於遍歷巢狀資料結構以及搜尋或排序演算法。

• 二叉樹遍歷、堆排序和查詢最短路徑是一些使用遞迴的例子。

使用遞迴計算階乘

遞迴最流行的例子是計算階乘。階乘在數學上定義為：

n! = n × (n-1)!

可以看出，我們使用階乘本身來定義階乘。因此，這是一個適合編寫遞迴函式的例子。

讓我們展開上述定義，計算 5 的階乘值

5! = 5 × 4!
      5 × 4 × 3!
      5 × 4 × 3 × 2!
      5 × 4 × 3 ×  2 × 1!
      5 × 4 × 3 ×  2 × 1
   = 120

雖然我們可以使用迴圈來執行此計算，但它的遞迴函式涉及連續呼叫自身，每次遞減數字，直到它達到 1。

示例

以下是計算階乘的遞迴函式。

<?php
   function factorial ($n) {
      if ($n == 1) {
         echo $n . PHP_EOL;
         return 1;
      } else {
         echo "$n * ";
         return $n*factorial($n-1);
      }
   }
   echo "Factorial of 5 = " . factorial(5);
?>

它將產生以下 **輸出**：

5 * 4 * 3 * 2 * 1
Factorial of 5 = 120

使用遞迴進行二分查詢

讓我們再看一個例子來了解遞迴是如何工作的。手頭的問題是檢查給定數字是否在一個列表中。

雖然我們可以使用 **for** 迴圈並比較每個數字來對列表中的某個數字進行順序搜尋，但順序搜尋效率不高，尤其是在列表過大的情況下。在這裡，我們可以使用二分查詢演算法，該演算法檢查索引 'high' 是否大於索引 'low'。根據 'mid' 變數中存在的值，再次呼叫該函式以搜尋元素。

我們有一個數字列表，按升序排列。然後，我們找到列表的中點，並將檢查限制為中點的左側或右側，具體取決於所需數字是否小於或大於中點的數字。

下圖顯示了二分查詢的工作原理：

示例

以下程式碼實現了遞迴二分搜尋技術：

<?php
   function bsearch($my_list, $low, $high, $elem) {
      if ($high >= $low) {
         $mid = intval(($high + $low)/2);

         if ($my_list[$mid] == $elem)
         return $mid;

         elseif ($my_list[$mid] > $elem)
         return bsearch($my_list, $low, $mid - 1, $elem);

         else
         return bsearch($my_list, $mid + 1, $high, $elem);
      }
      else
      return -1;
   }

   $list = [5,12,23, 45, 49, 67, 71, 77, 82];
   $num = 67;
   $result = bsearch($list,0,count($list)-1, $num);
   if ($result != -1)
   echo " Number $num found at index " . $result;
   else
   echo "Element not found!";
?>

它將產生以下 **輸出**：

Number 67 found at index 5

您可以檢查給定列表中存在的不同數字以及列表中不存在的數字的輸出。