核心要點(diǎn)

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

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

<?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ù)的結(jié)果，上面的函數(shù)使用簡單的循環(huán)計算任何給定數(shù)字的階乘。現(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);
}

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

什麼是遞歸？

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

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

遞歸類型

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

<?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ù)如何通過另一個函數(shù)間接調(diào)用自身。調(diào)用 A(n>4) 或 B(n>4) 會導(dǎo)致從另一個函數(shù)調(diào)用調(diào)用的函數(shù)。重要的是要知道函數(shù)可以像這樣間接調(diào)用自身，但在本文中，我們只處理直接遞歸。

一個實(shí)際的例子

為了向您展示遞歸的強(qiáng)大功能，我們將編寫一個在數(shù)組中搜索鍵並返回結(jié)果的函數(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ù)無限運(yùn)行的基例/保護(hù)子句
        return simple value;
    }
    else {
        // 使用更簡單的參數(shù)再次調(diào)用函數(shù)
        my_recursive_func(argsSimplified);
    }
}

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

頭遞歸和尾遞歸

在我們迄今為止的所有示例中，我們一直在使用所謂的頭遞歸。當(dāng)函數(shù)調(diào)用自身時，它會在返回自身值之前等待來自調(diào)用的結(jié)果?？梢跃帉懞瘮?shù)，使其不操作返回值，而是將所有必需的值作為參數(shù)傳遞。這稱為尾調(diào)用（或尾遞歸）。此方法通常是首選，因?yàn)檎Z言的運(yùn)行時有時可以優(yōu)化調(diào)用，因此不會有爆破調(diào)用堆棧的危險，但 PHP 不會這樣做。以下是我們的階乘示例，修改為進(jìn)行尾調(diào)用。請注意，返回遞歸調(diào)用的結(jié)果，而不是進(jì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);

一般建議

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

結(jié)論

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

圖片來自 Alexandre Duret-Lutz 通過 Flickr

關(guān)於理解 PHP 中遞歸的常見問題解答 (FAQ)

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

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

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

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

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

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

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

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

什麼是 PHP 中的尾遞歸？

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

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

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

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

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

什麼是 PHP 中的互遞歸？

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

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

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

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

雖然遞歸可以成為 PHP 中的強(qiáng)大工具，但它確實(shí)有一些限制。主要限制之一是如果遞歸太深，則存在堆棧溢出的風(fēng)險。這是因?yàn)槊看芜f歸調(diào)用都會在調(diào)用堆棧中添加一個新層，並且堆棧大小是有限的。由於函數(shù)調(diào)用的開銷，遞歸也可能比迭代解決方案慢，並且會使用更多內(nèi)存。此外，遞歸函數(shù)可能比迭代解決方案更難理解和調(diào)試。

以上是PHP主|了解遞歸的詳細(xì)內(nèi)容。更多資訊請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！