PHP - 遞歸函數

您好，有志於编程的各位！今天，我們將要深入探索PHP中遞歸函數的迷人世界。如果您是编程新手，請不要擔心；我會一步步地引導您了解這個概念，就像這些年來我對無數學生所做的一樣。所以，來一杯咖啡（或者您最喜歡的飲料），讓我們一起踏上這次令人興奮的旅程！

PHP - Recursive Functions

遞歸函數是什麼？

在我們深入細節之前，讓我們先了解遞歸函數是什麼。想像您正在鏡子前看自己，而您背後還有另一面鏡子。您會看到無限的自己倒影，對吧？這與程序設計中的遞歸函數的工作原理有些類似！

遞歸函數是一種在其執行過程中調用自己的函數。這就像俄羅斯套娃的數字版本，每個娃娃內部都包含一個較小的自己版本。

為什麼使用遞歸函數？

您可能會想，"為什麼我要讓一個函數調用自己？這不是會很混亂嗎？" 事實上，遞歸函數對於解決具有重複結構的問題非常有用。它們可以使我們的代碼更精緻，對某些類型的問題來說更容易理解。

讓我們看一個簡單的例子來濕一下腳：

function countDown($n) {
if ($n <= 0) {
echo "Blastoff!";
} else {
echo $n . "... ";
countDown($n - 1);
}
}

countDown(5);

如果我們用 countDown(5) 執行這個函數，會發生以下情況：

它打印 "5... "
然後用 4 調用自己
打印 "4... "
用 3 調用自己
依此类推，直到達到 0 並打印 "Blastoff!"

輸出會是："5... 4... 3... 2... 1... Blastoff!"

遞歸函數的結構

每個遞歸函數都有兩個主要部分：

基礎情況：這是停止遞歸的條件。沒有它，您的函數會永遠調用自己（或者直到您的計算機耗盡內存）！
遞歸情況：這是函數調用自己的地方，通常會有一個修改過的參數。

在我們的倒數計時例子中，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 邏輯與 (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