PHP - 递归函数

你好，有抱负的程序员们！今天，我们将深入探索PHP中递归函数的迷人世界。如果你是编程新手，不用担心；我会一步步引导你理解这个概念，就像我多年来教导无数学生一样。所以，拿一杯咖啡（或者你最喜欢的饮料），让我们一起踏上这段激动人心的旅程！

PHP - Recursive Functions

什么是递归函数？

在我们深入研究之前，先来了解一下递归函数是什么。想象你在镜子前看自己，而你的背后还有另一面镜子。你会看到自己的无限倒影，对吧？这在某种程度上类似于编程中递归函数的工作原理！

递归函数是在执行过程中调用自身的函数。这就像俄罗斯套娃的数字版本，每个娃娃里面都包含一个更小的自己。

为什么使用递归函数？

你可能会想，“为什么我要让一个函数调用自己？这不会很混乱吗？” 事实上，递归函数对于解决具有重复结构的问题非常有用。它们可以使我们的代码在某些类型的问题上更加优雅、易于理解。

让我们通过一个简单的例子来了解一下：

function countDown($n) {
if ($n <= 0) {
echo "发射！";
} else {
echo $n . "... ";
countDown($n - 1);
}
}

countDown(5);

如果我们用 countDown(5) 运行这个函数，会发生以下情况：

它打印 "5... "
然后用 4 调用自身
打印 "4... "
用 3 调用自身
如此循环，直到达到 0 并打印 "发射！"

输出将是："5... 4... 3... 2... 1... 发射！"

递归函数的解剖

每个递归函数都有两个主要部分：

基本情况：这是停止递归的条件。没有它，你的函数会永远调用自己（或者直到你的电脑内存耗尽）！
递归情况：这是函数调用自身的地方，通常带有修改过的参数。

在我们的倒计时示例中，if ($n <= 0) 是基本情况，而 countDown($n - 1) 是递归情况。

使用递归计算阶乘

现在我们已经掌握了基础知识，来解决一个经典问题：计算阶乘。一个数 n 的阶乘（写作 n!）是所有小于或等于 n 的正整数的乘积。

例如： 5! = 5 4 3 2 1 = 120

以下是如何使用递归计算阶乘的方法：

function factorial($n) {
if ($n <= 1) {
return 1;
} else {
return $n * factorial($n - 1);
}
}

echo factorial(5); // 输出：120

让我们分解一下：

我们的基本情况是 if ($n <= 1)。我们知道 1! 和 0! 都等于 1，所以在这种情况下我们返回 1。
对于任何其他数，我们将其乘以 (n-1) 的阶乘。

当我们调用 factorial(5) 时，以下是幕后发生的情况：

factorial(5) = 5 * factorial(4)
= 5 * (4 * factorial(3))
= 5 * (4 * (3 * factorial(2)))
= 5 * (4 * (3 * (2 * factorial(1))))
= 5 * (4 * (3 * (2 * 1)))
= 5 * (4 * (3 * 2))
= 5 * (4 * 6)
= 5 * 24
= 120

这个函数不断调用自己，直到达到基本情况，然后结果逐级返回，这不是很美吗？

使用递归实现二分搜索

现在，让我们升级难度，看看一个更复杂的例子：二分搜索。二分搜索是一种在有序列表中高效查找元素的方法。它通过反复将可能包含元素的部分列表分成两半，直到将可能的位置缩小到只有一个。

以下是如何使用递归实现二分搜索的方法：

function binarySearch($arr, $left, $right, $x) {
if ($right >= $left) {
$mid = $left + floor(($right - $left) / 2);

// 如果元素正好在中间
if ($arr[$mid] == $x) {
return $mid;
}

// 如果元素小于中间值，那么它只能出现在左子数组中
if ($arr[$mid] > $x) {
return binarySearch($arr, $left, $mid - 1, $x);
}

// 否则，元素只能出现在右子数组中
return binarySearch($arr, $mid + 1, $right, $x);
}

// 当元素不在数组中时，我们会到达这里
return -1;
}

$arr = [2, 3, 4, 10, 40];
$x = 10;
$result = binarySearch($arr, 0, count($arr) - 1, $x);
echo ($result == -1) ? "元素不在数组中" : "元素位于索引 " . $result;

这个函数一开始可能看起来令人畏惧，但让我们分解一下：

我们首先检查右索引是否大于或等于左索引。这是我们的继续条件。
我们计算中间索引。
如果中间元素是我们的目标，我们就完成了！
如果中间元素大于我们的目标，我们递归地在左半部分搜索。
如果中间元素小于我们的目标，我们递归地在右半部分搜索。
如果我们已经耗尽搜索（右 < 左），我们返回 -1 以指示未找到元素。

这种递归方法的优美之处在于它自然地将问题分解为更小的子问题，一旦你掌握了这个概念，代码就会变得优雅且易于理解。

结论

递归函数一开始可能看起来有点令人困惑，但它们是程序员工具箱中非常强大的工具。它们允许我们用优雅、简洁的代码解决复杂的问题。随着更多的练习，你会开始识别哪些问题适合递归解决方案。

记住，就像任何强大的工具一样，递归应该谨慎使用。有时，迭代解决方案可能更有效或更容易理解。随着经验的增长，你会培养出何时使用递归以及何时使用其他方法的直觉。

继续编码，不断尝试，最重要的是，享受乐趣！编程既是一门艺术，也是一门科学，掌握递归等概念将帮助你创建出美丽、高效的代码。下次见，祝编码愉快！

方法	描述	示例
countDown()	从给定数字倒数到零	countDown(5)
factorial()	计算给定数字的阶乘	factorial(5)
binarySearch()	在有序数组中搜索元素	binarySearch($arr, 0, count($arr) - 1, $x)

Credits: Image by storyset