Php 简明教程

PHP - Recursive Functions

递归函数是一种在满足特定条件之前不断调用自身的函数。在 PHP 中，可以定义递归函数。

  1. 当某个问题通过其自身来定义时，就使用递归。

  2. 有时，使用迭代方法解决问题可能会很乏味。递归方法为看似复杂的问题提供了非常简洁的解决方案。

  3. PHP 中的递归与 C 和 C++ 中的递归非常相似。

  4. 在遍历嵌套数据结构，以及排序算法或搜索算法中，特别使用递归函数。

  5. 二叉树遍历、堆排序和寻找最短路径是使用递归的一些情况。

Calculation of Factorial using Recursion

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

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。

Example

以下为计算阶乘的递归函数。

<?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);
?>

它将生成以下 output −

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

Binary Search using Recursion

让我们看另一个理解递归工作原理的示例。眼前的问题是检查给定数字是否存在于列表中。

虽然我们可以使用 for 循环并比较每个数字，对列表中的特定数字执行顺序查找，但顺序查找效率不高，尤其是在列表过大的情况下。在此，我们可以使用二分查找算法检查索引“high”是否大于索引“low”。根据“mid”变量中存在的值，再次调用该函数以搜索该元素。

我们有一个数字列表，按升序排列。然后，找到列表的中点，并将检查限制在中点的左侧或右侧，具体取决于所需的数字是否小于或大于中点的数字。

下图显示了二分查找的工作原理 -

php recursive functions

Example

以下代码实现了递归二分查找技术 -

<?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!";
?>

它将生成以下 output −

Number 67 found at index 5

你可以查看给定列表中存在的不同数字的输出，以及列表中不存在的数字的输出。