PHP - 递归函数

递归函数就是这样一个函数，它会调用自身直到满足某个条件。在 PHP 中，可以定义递归函数。

• 当某个问题根据自身来定义时，使用递归。
• 有时，使用迭代方法解决问题可能很乏味。递归方法为看似复杂的问题提供了一个非常简洁的解决方案。
• PHP 中的递归与 C 和 C++ 中的递归非常相似。
• 递归函数特别用于遍历嵌套数据结构以及搜索或排序算法。
• 二叉树遍历、堆排序和寻找最短路线是使用递归的一些情况。

使用递归计算阶乘

递归最流行的示例是阶乘计算。在数学上，阶乘定义为 -

 n! = n × (n-1)!

可以看出，我们使用 factorial 本身来定义 factorial。因此，这是编写递归函数的合适情况。

让我们扩展上述定义以计算 5 的阶乘值

虽然我们可以使用循环来执行此计算，但其递归函数涉及通过递减数字直到达到 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);
?>

它将产生以下输出 -

使用递归进行二叉搜索

让我们看另一个例子来了解递归是如何工作的。手头的问题是检查列表中是否存在给定的数字。

虽然我们可以使用 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!";
?>

它将产生以下输出 -

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