核心要點(diǎn)

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

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

<?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;
}

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

<?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)用這兩個(gè)函數(shù)時(shí)，我們得到相同的結(jié)果，但是請(qǐng)注意，第二個(gè)函數(shù)通過(guò)調(diào)用自身來(lái)計(jì)算階乘。這被稱為遞歸。

什么是遞歸？

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

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

遞歸類型

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

<?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í)際上是無(wú)用的代碼，只是為了向您展示函數(shù)如何通過(guò)另一個(gè)函數(shù)間接調(diào)用自身。調(diào)用 A(n>4) 或 B(n>4) 會(huì)導(dǎo)致從另一個(gè)函數(shù)調(diào)用調(diào)用的函數(shù)。重要的是要知道函數(shù)可以像這樣間接調(diào)用自身，但在本文中，我們只處理直接遞歸。

一個(gè)實(shí)際的例子

為了向您展示遞歸的強(qiáng)大功能，我們將編寫一個(gè)在數(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);
}

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

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

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

頭遞歸和尾遞歸

在我們迄今為止的所有示例中，我們一直在使用所謂的頭遞歸。當(dāng)函數(shù)調(diào)用自身時(shí)，它會(huì)在返回自身值之前等待來(lái)自調(diào)用的結(jié)果?？梢跃帉懞瘮?shù)，使其不操作返回值，而是將所有必需的值作為參數(shù)傳遞。這稱為尾調(diào)用（或尾遞歸）。此方法通常是首選，因?yàn)檎Z(yǔ)言的運(yùn)行時(shí)有時(shí)可以優(yōu)化調(diào)用，因此不會(huì)有爆破調(diào)用堆棧的危險(xiǎn)，但 PHP 不會(huì)這樣做。以下是我們的階乘示例，修改為進(jìn)行尾調(diào)用。請(qǐng)注意，返回遞歸調(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) 排序時(shí)非常出色。當(dāng)您需要?jiǎng)澐种貜?fù)性問(wèn)題時(shí)，遞歸比迭代方法更適合，例如在文件系統(tǒng)中搜索，并且您還需要進(jìn)入任何子目錄進(jìn)行搜索。在遍歷不確定深度的地方，遞歸效果很好。請(qǐng)記住，PHP 不會(huì)優(yōu)化遞歸函數(shù)，即使您編寫它們以進(jìn)行尾調(diào)用，遞歸函數(shù)通常也比其迭代對(duì)應(yīng)函數(shù)效率低且速度慢，盡管它們有時(shí)可以更好地完成工作，如上面的代碼示例所示。遞歸通常是函數(shù)式編程中迭代的首選替代方法，因此大多數(shù)函數(shù)式語(yǔ)言都會(huì)優(yōu)化遞歸函數(shù)。如果您使用的是 XDebug，請(qǐng)務(wù)必檢查您系統(tǒng)的配置。默認(rèn)情況下，您將限制 100 次遞歸調(diào)用，如果您超過(guò)此限制，您的腳本將拋出“已達(dá)到最大嵌套限制”錯(cuò)誤。如果您需要更改此設(shè)置，可以更新 debug.max_nesting_level 配置值。最后，最好閱讀堆棧堆和遞歸導(dǎo)致堆棧溢出的解釋，以了解在遞歸期間調(diào)用堆棧會(huì)發(fā)生什么情況。

結(jié)論

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

圖片來(lái)自 Alexandre Duret-Lutz 通過(guò) Flickr

關(guān)于理解 PHP 中遞歸的常見(jiàn)問(wèn)題解答 (FAQ)

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

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

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

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

PHP 中的所有問(wèn)題都可以使用遞歸來(lái)解決嗎？

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

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

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

什么是 PHP 中的尾遞歸？

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

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

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

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

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

什么是 PHP 中的互遞歸？

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

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

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

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

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

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