PHP資料結構基礎之遞歸

這篇文章主要介紹了關於PHP資料結構基礎之遞歸，有著一定的參考價值，現在分享給大家，有需要的朋友可以參考一下

什麼是遞歸？

之前說到，遞歸是一種將大問題分解為小問題的解決方案。一般來說，遞歸稱為函數自身的呼叫。這麼說可能聽起來很奇怪，事實上在遞歸中，函數確實必須呼叫自己。

一個栗子

例如在數學中，我們都知道「階乘」的概念。例如5的階乘就是5*4*3*2*1。

• 5！ = 5 * 4！

• 4！ = 4 * 3！

• 3！ = 3 * 2！

• 2！ = 2 * 1！

• 1！ = 1 * 0！

• 0！ = 1

我們可以總結求n的階乘的規律，即 n! = n * (n -1) !

這就體現了遞迴。你可以從中發現，我們把求5的階乘一步一步轉化成了另外一個個的小問題。

遞迴演算法的特性

• 每一個遞迴呼叫都必須基於一個小的子問題。例如5的階乘就是5乘4的階乘。

• 遞迴必須有一個Base case。例如階乘的Base case就是0，當條件是0的時候，就停止遞歸。

• 遞歸中避免循環調用，否則最後電腦會顯示堆疊溢出的錯誤。

function factorial(int $n): int
{
    if ($n = 0) {
        return 1;
    }
    
    return $n * factorial($n - 1);
}

看上面的程式碼，我們可以看到對於階乘問題的解我們有一個基礎的條件就是當n為0的時候，我們回傳1。如果不符合這個條件，我們回傳n 乘 factorial(n) ，這符合遞迴特性的第一條和第三條。我們避免了循環調用，因為我們把每一次的遞歸調用都分解成了大問題的一個小的子問題。上面的演算法思想可以表達成：

遞迴Vs迭代

上面的遞歸程式碼我們同樣可以用迭代的方法實作

function factorial(int $n): int
{
    $result = 1;
    
    for ($i = $n; $i > 0; $i--) {
        $result*= $n;
    }
    
    return $result;
}

如果一個問題可以很容易的使用迭代來解決，我們為何要使用遞歸？

遞歸是用來處理更複雜的問題的，不是所有的問題都可以簡單的使用迭代來解決的。遞歸使用函數呼叫來管理呼叫棧，所以相比於迭代遞歸會使用更多和時間以及記憶體。此外，在迭代中，我們每一步都會有一個結果，但是在遞迴中我們必須等到base case執行結束才會有任何結果。看上面的例子，我們發現在遞歸演算法中我們沒有任何變數或聲明來保存結果，而在迭代演算法中，我們每次都用$result來保存了回傳結果。

斐波那契數列

在數學中，斐波那契數列是一個特殊的整數數列，數列中的每一個數的是由另外兩個數求和產生的。規則如下：

function fibonacci($n)
{
    if ($n == 0) {
        return 0;
    }
    
    if ($n == 1) {
        return 1;
    }
    
    return fibonacci($n - 1) + fibonacci($ - 2);
}

最大公因數

#另外一個使用遞迴演算法的常見問題是求兩個數的最大公因數。

function gcd(int $a, int $b)
{
    if ($b == 0) {
        return $a;
    }
    
    return gcd($b, $a % $b);
}

遞迴型別

• #線性遞迴

在每一次遞迴呼叫中，函數只呼叫自己一次，這就叫做線性遞歸。

• 二分遞迴

在二分遞迴中，每一次遞迴呼叫函數都會呼叫自己兩次。求解斐波那契數列的演算法就是二分遞歸，除此之外還有二分查找、分治演算法、歸併排序等也使用了二分遞歸。

• 尾遞歸

當一個遞迴回傳的時候沒有等待的操作的時候就稱為尾遞歸。在斐波那契演算法中，回傳值需要乘以前一個遞歸的回傳值，因此他不是尾遞歸，而解出最大公因式的演算法就是尾遞歸。尾遞歸是線性遞歸的一種形式。

• 相互遞歸

例如在每一次遞歸呼叫中有A() 呼叫B(), B() 呼叫A() ，這樣的遞歸就叫做相互遞歸。

• 巢狀遞迴

當一個遞迴函數把自己當作一個參數進行遞迴呼叫時，就叫做巢狀遞歸。一個常見的栗子就是阿克曼函數，看下面的表達。

看最後一行的，可以看到第二個參數就是遞迴函數自己。

下一節

下一篇內容會使用遞歸解決一些實際開發中會遇到的問題，例如建立N級分類、建立嵌套評論、目錄檔案的遍歷等等。

以上就是本文的全部內容，希望對大家的學習有所幫助，更多相關內容請關注PHP中文網！

相關推薦：

PHP取得客戶端真實IP位址的方法

PHP中使用Elasticsearch的方法

以上是PHP資料結構基礎之遞歸的詳細內容。更多資訊請關注PHP中文網其他相關文章！