PHP课程 - 第9课 - 递归

在上一课中，我们学习了 PHP 中函数的使用。现在，我们将更深入地了解函数的特性。之前我们使用的函数都是如下形式：

<?php
function myFunction(){ // 定义函数

}

$x = myFunction(); // 调用函数
?>

但是，如果在函数内部再次调用自己会怎样呢？

<?php
function myFunction(){
  $x = myFunction();
  ...
  return $x;
}

$y = myFunction();

这种在函数体内部调用自身的方式称为递归（recursion）。虽然听起来有点复杂，但理解起来其实并不难。

让我们编写一个递归函数，用来计算一个数的幂。你可能还记得代数中的定义：一个数的 n 次幂等于这个数自身相乘 n 次。在 PHP 中我们可以这样实现：

<?php
function myDegree($x, $n){
  if($n == 0){
	return 1;
  }
  if($n < 0){
    return myDegree(1/$x, -$n); // -$n 表示取相反数，将负次幂转换为正次幂
  }
  return $x * myDegree($x, $n-1); // 在函数内部调用自身
}

$y = myDegree(2, -4); // 第一次调用函数
print $y;
?>

现在我们逐步分析一下这个函数。首先要记住：在执行到 return 语句时，函数立即停止执行并返回结果。

第一段条件 if($n == 0)：当指数为 0 时，函数返回 1——这是数学上的规定。

第二段条件 if($n < 0)：当指数为负数时，我们将其转换为正数，同时将底数取倒数（即变成分数）。这是符合幂的定义的做法。

最后，如果指数既不是 0 也不是负数，就执行：

return $x * myDegree($x, $n-1);

也就是说，每次调用时将指数减 1，并将当前结果乘以 $x。这就是递归的核心。

让我们看看每次递归调用时的变化：

1. 初始：指数 -4，底数 2。
此时触发第二个 if，底数变为分数，指数改为正数。

2. 指数 4，底数 0.5。
指数为正且不为 0，因此执行：

return $x * myDegree($x, $n-1)

3. 指数 3，底数 0.25。
4. 指数 2，底数 0.125。
5. 指数 1，底数 0.0625。
当指数减到 0 时，触发第一个 if，返回 1。然后所有递归返回的值相乘，最终得到结果。

再看一个类似的例子——求一个数的阶乘。阶乘 n! 等于 1 到 n 所有数的乘积。例如 6! = 6×5×4×3×2×1 = 720。这里同样可以用递归实现：

<?php
function myRecursion($x){
  if($x == 1){
    return $x;
  }
  return $x * myRecursion($x-1);
}

$y = myRecursion(8);
print $y;
?>

这个例子比上一个更简单，留作练习：试着自己跟踪每一步函数调用时参数的变化，理解递归是如何逐步计算出最终结果的。