核心要點

• 遞歸是一種問題解決方法，它涉及函數(shù)直接或間接地（通過函數(shù)調用循環(huán)）調用自身。它在遍歷樹和列表或執(zhí)行大多數(shù) O(n log n) 排序時特別有用。
• 遞歸函數(shù)必須有一個基例或保護子句，以防止它們無限地調用自身，從而導致堆棧溢出錯誤。此基例是在滿足特定條件時停止函數(shù)進行進一步遞歸調用的條件。
• 遞歸有兩種類型：直接遞歸和間接遞歸。直接遞歸是指函數(shù)直接調用自身，而間接遞歸是指函數(shù)通過另一個函數(shù)間接調用自身。本文重點介紹直接遞歸。
• 雖然遞歸可以是一種強大的工具，但必須謹慎使用。PHP 不會優(yōu)化遞歸函數(shù)，它們通常不如其迭代對應函數(shù)高效和快速。但是，在某些情況下，例如在文件系統(tǒng)中搜索或遍歷不確定深度時，遞歸可能更有效。

在我之前的一篇文章中，我寫過關于迭代器以及如何使用它們。今天，我想看看迭代的同胞兄弟：遞歸。不過，在我們討論遞歸之前，讓我們先看看這段代碼：

<?php
function factorial($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    $factorial = 1; 
    while ($number > 0) {
        $factorial *= $number;
        $number--;
    }
    return $factorial;
}

階乘是一個數(shù)乘以小于該數(shù)的所有正整數(shù)的結果，上面的函數(shù)使用簡單的循環(huán)計算任何給定數(shù)字的階乘?，F(xiàn)在讓我們這樣重寫這個例子：

<?php
function factorial_recursive($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    if ($number == 0) {
        return 1;
    }
    return $number * factorial_recursive($number - 1);
}

當我們調用這兩個函數(shù)時，我們得到相同的結果，但是請注意，第二個函數(shù)通過調用自身來計算階乘。這被稱為遞歸。

什么是遞歸？

遞歸函數(shù)是指直接或通過函數(shù)調用循環(huán)調用自身的函數(shù)。遞歸也可以指一種問題解決方法，它首先解決問題的較小版本，然后使用該結果加上一些其他計算來形成對原始問題的答案。通常，在解決較小版本的過程中，該方法將解決更小版本的難題，依此類推，直到達到易于解決的“基例”。要編寫遞歸函數(shù)，您需要為其提供某種返回方法，否則它將永遠（或直到調用堆棧爆裂、腳本超時或內存耗盡）不斷調用自身。這被稱為保護子句或基例。遞歸函數(shù)的最簡單形式如下：

<?php
function my_recursive_func(args) {
    if (simplest case) {
        // 停止函數(shù)無限運行的基例/保護子句
        return simple value;
    }
    else {
        // 使用更簡單的參數(shù)再次調用函數(shù)
        my_recursive_func(argsSimplified);
    }
}

遞歸類型

當函數(shù)直接調用自身時，稱為直接遞歸。函數(shù)在一個函數(shù)調用循環(huán)中最終調用自身稱為間接遞歸。請查看下面間接遞歸的示例：

<?php
function A($num) {
    $num -= 1;
    if($num > 0) {  
        echo "A is Calling B($num)\n";
        $num = B($num);
    }
    return $num;
}

function B($num) {
    $num -= 2;
    if($num > 0) {
        echo "B is Calling A($num)\n";
        $num = A($num);
    }
    return $num;
}

$num = 4;
echo "Calling A($num)\n";
echo 'Result: ' . A($num);

<code>Calling A(4)
A is Calling B(3)
B is Calling A(1)
Result: 0</code>

上面的例子實際上是無用的代碼，只是為了向您展示函數(shù)如何通過另一個函數(shù)間接調用自身。調用 A(n>4) 或 B(n>4) 會導致從另一個函數(shù)調用調用的函數(shù)。重要的是要知道函數(shù)可以像這樣間接調用自身，但在本文中，我們只處理直接遞歸。

一個實際的例子

為了向您展示遞歸的強大功能，我們將編寫一個在數(shù)組中搜索鍵并返回結果的函數(shù)。

<?php
function factorial($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    $factorial = 1; 
    while ($number > 0) {
        $factorial *= $number;
        $number--;
    }
    return $factorial;
}

<?php
function factorial_recursive($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    if ($number == 0) {
        return 1;
    }
    return $number * factorial_recursive($number - 1);
}

一切都很順利，但是請注意，我們只迭代到數(shù)組的第二層，因此在第三層中搜索“Fibonacci”失敗了。如果我們要搜索不確定深度的數(shù)組，這將不夠用。我們可以將搜索重寫為遞歸函數(shù)：

<?php
function my_recursive_func(args) {
    if (simplest case) {
        // 停止函數(shù)無限運行的基例/保護子句
        return simple value;
    }
    else {
        // 使用更簡單的參數(shù)再次調用函數(shù)
        my_recursive_func(argsSimplified);
    }
}

使用遞歸函數(shù)，我們可以搜索幾層深的數(shù)組，因為我們沒有硬編碼函數(shù)的深度。它只是不斷運行，直到遍歷數(shù)組中的所有值。

頭遞歸和尾遞歸

在我們迄今為止的所有示例中，我們一直在使用所謂的頭遞歸。當函數(shù)調用自身時，它會在返回自身值之前等待來自調用的結果。可以編寫函數(shù)，使其不操作返回值，而是將所有必需的值作為參數(shù)傳遞。這稱為尾調用（或尾遞歸）。此方法通常是首選，因為語言的運行時有時可以優(yōu)化調用，因此不會有爆破調用堆棧的危險，但 PHP 不會這樣做。以下是我們的階乘示例，修改為進行尾調用。請注意，返回遞歸調用的結果，而不是進一步操作它。

<?php
function A($num) {
    $num -= 1;
    if($num > 0) {  
        echo "A is Calling B($num)\n";
        $num = B($num);
    }
    return $num;
}

function B($num) {
    $num -= 2;
    if($num > 0) {
        echo "B is Calling A($num)\n";
        $num = A($num);
    }
    return $num;
}

$num = 4;
echo "Calling A($num)\n";
echo 'Result: ' . A($num);

一般建議

任何可以用迭代方式編寫的代碼也可以用遞歸方式編寫。但是，這并不總是容易做到（甚至明智）。遞歸在遍歷樹和列表或執(zhí)行大多數(shù) O(n log n) 排序時非常出色。當您需要劃分重復性問題時，遞歸比迭代方法更適合，例如在文件系統(tǒng)中搜索，并且您還需要進入任何子目錄進行搜索。在遍歷不確定深度的地方，遞歸效果很好。請記住，PHP 不會優(yōu)化遞歸函數(shù)，即使您編寫它們以進行尾調用，遞歸函數(shù)通常也比其迭代對應函數(shù)效率低且速度慢，盡管它們有時可以更好地完成工作，如上面的代碼示例所示。遞歸通常是函數(shù)式編程中迭代的首選替代方法，因此大多數(shù)函數(shù)式語言都會優(yōu)化遞歸函數(shù)。如果您使用的是 XDebug，請務必檢查您系統(tǒng)的配置。默認情況下，您將限制 100 次遞歸調用，如果您超過此限制，您的腳本將拋出“已達到最大嵌套限制”錯誤。如果您需要更改此設置，可以更新 debug.max_nesting_level 配置值。最后，最好閱讀堆棧堆和遞歸導致堆棧溢出的解釋，以了解在遞歸期間調用堆棧會發(fā)生什么情況。

結論

在本文中，我向您廣泛介紹了遞歸及其與迭代的比較。我還向您展示了如何編寫遞歸函數(shù)、何時編寫它們以及原因。我還試圖警告您使用遞歸時可能會遇到的一些陷阱。遞歸是這樣的，即使許多經驗豐富的程序員也可能多年不用它，而許多其他人甚至從未聽說過它，這令人遺憾，因為它是一個真正強大的概念。我希望通過這篇文章，我可以為您提供足夠的知識，讓您開始編寫自己的遞歸函數(shù)。但請記住，就像使用火一樣，您必須始終小心謹慎地使用此工具。

圖片來自 Alexandre Duret-Lutz 通過 Flickr

關于理解 PHP 中遞歸的常見問題解答 (FAQ)

PHP 遞歸函數(shù)中的基例是什么？

PHP 遞歸函數(shù)中的基例是阻止函數(shù)無限調用自身的條件。它是任何遞歸函數(shù)的關鍵部分。如果沒有基例，遞歸函數(shù)將無限地調用自身，導致堆棧溢出錯誤。在 PHP 中，基例通常使用函數(shù)開頭的“if”語句定義。函數(shù)在繼續(xù)進行遞歸調用之前檢查此條件。如果滿足條件，函數(shù)將返回一個值并停止調用自身。

PHP 中的遞歸函數(shù)是如何工作的？

PHP 中的遞歸函數(shù)通過在其自身函數(shù)體中調用自身，直到滿足稱為基例的特定條件。當調用遞歸函數(shù)時，它執(zhí)行特定任務，然后調用自身以重復該任務。此過程持續(xù)到滿足基例，此時函數(shù)停止調用自身。每次調用函數(shù)都會在調用堆棧上創(chuàng)建一個新層，存儲函數(shù)調用的變量和返回地址。一旦滿足基例，函數(shù)就開始返回，逐層解開調用堆棧。

PHP 中的所有問題都可以使用遞歸來解決嗎？

雖然遞歸可以成為 PHP 中的強大工具，但并非所有問題都可以或應該使用遞歸來解決。遞歸最適合可以分解成更小、更相似的問題的問題，例如遍歷文件目錄或對數(shù)組進行排序。但是，如果使用不當，遞歸會導致高內存使用率和堆棧溢出錯誤。由于函數(shù)調用的開銷，它通常也比迭代解決方案慢。因此，了解手頭的問題并選擇正確的方法非常重要。

如何防止 PHP 遞歸函數(shù)中的堆棧溢出？

可以通過仔細定義函數(shù)最終將達到的基例來防止遞歸函數(shù)中的堆棧溢出?；且粋€條件，當滿足此條件時，函數(shù)將停止進行進一步的遞歸調用。如果沒有基例，函數(shù)將無限地調用自身，導致堆棧溢出。同樣重要的是要確保每次遞歸調用都使函數(shù)更接近基例，以避免無限遞歸。

什么是 PHP 中的尾遞歸？

尾遞歸是一種特殊的遞歸，其中遞歸調用是函數(shù)中的最后一個操作。這意味著無需跟蹤之前的函數(shù)調用，允許編譯器或解釋器優(yōu)化遞歸并降低堆棧溢出的風險。但是，PHP 本身并不支持尾遞歸優(yōu)化。因此，雖然您可以在 PHP 中編寫尾遞歸函數(shù)，但它們不會被優(yōu)化，并且仍然會為每次遞歸調用消耗堆?？臻g。

PHP 中的遞歸與循環(huán)如何比較？

遞歸和循環(huán)都可以用于在 PHP 中重復一組指令。但是，它們的工作方式不同，并且具有不同的優(yōu)缺點。遞歸是解決可以分解成更小、更相似問題的復雜問題的強大工具。它對于遍歷樹或圖之類的任務特別有用。另一方面，循環(huán)通常更適合簡單的重復性任務。它們比遞歸使用更少的內存，并且不太可能導致堆棧溢出。

我可以使用遞歸來遍歷 PHP 中的數(shù)組嗎？

是的，遞歸可以成為遍歷 PHP 中數(shù)組（尤其是多維數(shù)組）的非常有效的方法?？梢允褂眠f歸函數(shù)迭代數(shù)組中的每個元素，如果元素本身也是數(shù)組，則函數(shù)可以調用自身來迭代該數(shù)組。此過程持續(xù)到訪問所有元素為止。但是，請記住，遞歸可能比迭代解決方案慢，并且會使用更多內存，尤其是在大型數(shù)組的情況下。

什么是 PHP 中的互遞歸？

互遞歸是指兩個或多個函數(shù)以循環(huán)方式相互調用。在 PHP 中，這意味著函數(shù) A 調用函數(shù) B，而函數(shù) B 調用函數(shù) A。這可以成為解決某些類型問題的強大工具，但它也可能比簡單的遞歸更難理解和調試。與任何遞歸函數(shù)一樣，重要的是定義一個基例以防止無限遞歸。

如何調試 PHP 中的遞歸函數(shù)？

由于函數(shù)多次調用自身，因此調試 PHP 中的遞歸函數(shù)可能具有挑戰(zhàn)性。但是，您可以使用多種策略。一種方法是使用打印語句或調試器來跟蹤函數(shù)調用并查看每個步驟中變量的狀態(tài)。另一種方法是繪制遞歸樹以可視化函數(shù)調用。同樣重要的是要仔細檢查基例和遞歸情況以確保它們是正確的。

使用 PHP 中的遞歸有什么限制？

雖然遞歸可以成為 PHP 中的強大工具，但它確實有一些限制。主要限制之一是如果遞歸太深，則存在堆棧溢出的風險。這是因為每次遞歸調用都會在調用堆棧中添加一個新層，并且堆棧大小是有限的。由于函數(shù)調用的開銷，遞歸也可能比迭代解決方案慢，并且會使用更多內存。此外，遞歸函數(shù)可能比迭代解決方案更難理解和調試。

以上是PHP主|了解遞歸的詳細內容。更多信息請關注PHP中文網其他相關文章！