PHP主|了解遞歸

核心要點

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

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

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

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

什麼是遞歸？

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

<?php
function my_recursive_func(args) {
    if (simplest case) {
        // 停止函数无限运行的基例/保护子句
        return simple value;
    }
    else {
        // 使用更简单的参数再次调用函数
        my_recursive_func(argsSimplified);
    }
}

遞歸類型

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

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

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

一個實際的例子

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

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

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

<?php
function my_recursive_func(args) {
    if (simplest case) {
        // 停止函数无限运行的基例/保护子句
        return simple value;
    }
    else {
        // 使用更简单的参数再次调用函数
        my_recursive_func(argsSimplified);
    }
}

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

頭遞歸和尾遞歸

在我們迄今為止的所有示例中，我們一直在使用所謂的頭遞歸。當函數調用自身時，它會在返回自身值之前等待來自調用的結果。可以編寫函數，使其不操作返回值，而是將所有必需的值作為參數傳遞。這稱為尾調用（或尾遞歸）。此方法通常是首選，因為語言的運行時有時可以優化調用，因此不會有爆破調用堆棧的危險，但 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);

一般建議

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

結論

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

圖片來自 Alexandre Duret-Lutz 通過 Flickr

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

PHP 遞歸函數中的基例是什麼？

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

PHP 中的遞歸函數是如何工作的？

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

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

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

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

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

什麼是 PHP 中的尾遞歸？

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

PHP 中的遞歸與循環如何比較？

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

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

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

什麼是 PHP 中的互遞歸？

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

如何調試 PHP 中的遞歸函數？

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

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

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

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