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

您可以检查给定列表中存在的不同数字以及列表中不存在的数字的输出。