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

例如在數學中，我們都知道“階乘”的概念。例如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) ，這符合遞歸特性的第一條和第三條。我們避免了循環調用，因為我們把每一次的遞歸調用都分解成了大問題的一個小的子問題。上面的算法思想可以表達成：

上面的遞歸代碼我們同樣可以使用迭代的方法實現

function%20factorial(int%20$n):%20int%20$result%20=%201;%20for%20($i%20=%20$n;%20$i%20$i--)%20{%20$result*=%20$n;%20return%20$result;}

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

遞歸是用來處理更加復雜的問題的，不是所有的問題都可以簡單的使用迭代來解決的。遞歸使用函數調用來管理調用棧，所以相比于迭代遞歸會使用更多和時間以及內存。此外，在迭代中，我們每一步都會有一個結果，但是在遞歸中我們必須等到base%20case執行結束才會有任何結果。看上面的例子，我們發現在遞歸算法中我們沒有任何變量或者聲明來保存結果，而在迭代算法中，我們每一次都用$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教程

鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯系我們修改或刪除，多謝。