Php 简明教程

PHP - Recursive Functions

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

A recursive function is such a function that calls itself until a certain condition is satisfied. In PHP, it is possible to defines a recursive function.

  1. Recursion is used when a certain problem is defined in terms of itself.

  2. Sometimes, it can be tedious to solve a problem using iterative approach. Recursive approach provides a very concise solution to seemingly complex problems.

  3. Recursion in PHP is very similar to the one in C and C++.

  4. Recursive functions are particularly used in traversing nested data structures, and searching or sorting algorithms.

  5. Binary tree traversal, heap sort and finding shortest route are some of the cases where recursion is used.

Calculation of Factorial using Recursion

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

The most popular example of recursion is calculation of factorial. Mathematically factorial is defined as −

n! = n × (n-1)!

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

It can be seen that we use factorial itself to define factorial. Hence, this is a fit case to write a recursive function.

让我们展开上述定义,计算 5 的阶乘值

Let us expand the above definition for calculation of factorial value of 5

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

虽然我们可以使用循环执行此计算,但其递归函数涉及通过递减数字依次调用它,直到数字变为 1。

While we can perform this calculation using a loop, its recursive function involves successively calling it by decrementing the number till it reaches 1.

Example

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

Following is the recursive function to calculate factorial.

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

It will produce the following output

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

Binary Search using Recursion

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

Let us have a look at another example to understand how recursion works. The problem at hand is to check whether a given number is present in a list.

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

While we can perform a sequential search for a certain number in the list using a for loop and comparing each number, the sequential search is not efficient especially if the list is too large. Here, we can use the binary search algorithm that checks if the index 'high' is greater than index 'low. Based on the value present at 'mid' variable, the function is called again to search for the element.

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

We have a list of numbers, arranged in ascending order. Then, we find the midpoint of the list and restrict the checking to either left or right of midpoint depending on whether the desired number is less than or greater than the number at midpoint.

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

The following diagram shows how binary search works −

php recursive functions

Example

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

The following code implements the recursive binary searching technique −

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

It will produce the following output

Number 67 found at index 5

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

You can check the output for different numbers present in the given list, as well as those which are not present in the list.