javaScript 算法基礎知識第 4 部分：具有線性時間復雜度 O(n) 和指數時間復雜度 O(2^n) 的遞歸算法。遞歸是編程中的關鍵概念之一。作為一種解決問題的方法，它也被廣泛用于數據結構和算法中。它幫助我們將大型復雜問題分解為較小的問題。因此，了解遞歸的時間復雜性對于理解和提高代碼效率至關重要。

　　對于本系列 JavaScript 算法的第 3 部分，您可以參考以下鏈接。

　　第3部分：使用漸近分析推導恒定時間復雜度O(1)

　　在本文中，我們將介紹遞歸算法的兩個示例及其時間復雜度。

　　具有線性時間復雜度 O(n) 的遞歸算法

　　具有指數時間復雜度 O(2^n) 的遞歸算法

　　首先，簡要介紹一下遞歸。

　　什么是遞歸？

　　我們說一個函數是遞歸函數，如果它直接或間接地調用自己。下面是遞歸函數的一瞥。

　　上面的函數是遞歸函數的一個例子，因為它正在調用自身，但它也是不完整的，因為它會導致無限循環。這是因為該函數沒有任何退出條件。但是，這里的關鍵點是，遞歸只是從該函數內部調用該函數。

　　為了非常清楚地說明這一點，讓我們看一個簡單的例子。

　　示例問題

　　創建一個簡單的函數來計算輸入數字的階乘。

　　如果您不知道什么是階乘，請使用以下輸入查看以下函數的行為。

　　你拿輸入數字，乘以這個數字減去1，然后重復相同的操作，直到你達到1。這就是我們計算階乘的方式。而且，最后，我們可以編寫一個函數來做到這一點。

　　讓我們首先看一下非遞歸方法。因為遞歸通常(并非總是)只是常規循環的替代方法。因此，讓我們嘗試首先使用基于循環的方法解決它。

　　功能(基于循環的方法)

　　因此，這是一個使用正態循環的階乘函數。使用這樣的循環并不是解決階乘問題的壞方法。但也存在一種不同的方法來使用遞歸來解決上述問題。而且，正如您將進一步看到的那樣，這種遞歸將允許我們編寫更少的代碼，這通常是我們可能想要使用遞歸的原因之一。

　　遞歸解 O(n)

　　上面的函數是遞歸的，因為它正在調用自身。在函數中有兩件重要的事情要觀察，即“if block”和“函數調用”，參數為(n-1)。

　　我們將 if 塊稱為“退出條件”或始終返回值的“基本情況”。并且，將“函數調用”作為“遞歸步驟”。

　　另一件需要注意的重要事情是，我們在遞歸步驟中將不同的參數傳遞給函數調用。因為，如果我們再次調用帶有n的函數，我們將不會更改任何內容。我們只會得到一個無限循環。

　　因此，遞歸函數應始終具有這兩個組件，即“退出條件”和“遞歸步驟”，否則我們將始終具有無限循環，這將使我們的程序崩潰。

　　如果滿足基本條件，退出條件或基本情況為我們提供了一種退出函數的方法。

　　而且，遞歸步驟幫助我們通過對同一函數進行遞歸調用來計算結果，但輸入的大小減小。

　　這可以表示為函數調用鏈。就像下面的例子一樣，對于一個事實(4)，我們將返回4 * fact(3)，這給了我們3 * 個事實(2)，這將再次給我們2 * 個事實(1)。并且，這最終返回 1，然后將計算的返回值傳遞給函數調用，從而產生 24。

　　如何推導遞歸算法的時間復雜度？

　　根據漸近分析，我們仍然可以計算上述函數中的操作。因此，每個操作將執行一次，包括 return 語句中的函數調用。

　　但是，由于我們在 return 語句中有一個函數調用。我們啟動一個新的函數調用，因此函數中的所有代碼都會再次運行多次，直到滿足退出條件。因此，我們可以計算遞歸函數的函數調用次數。因此，我們可以看到，在上面的示例中，我們得到了 4 個函數調用，函數的階乘為 4。

　　在每個函數調用中，我們有一個常量時間，我們的函數中沒有任何循環。因此，我們可以將其編寫如下。

　　但是，上述函數調用觸發了多個函數調用，即當輸入值為n時，n個函數調用。

　　因此，我們對多個函數調用的時間復雜度將是，

　　那就是，

　　這可以寫成，

　　上面的等式最后只是O(n)。而且，這與我們基于循環的解決方案的時間復雜度相同，即線性時間復雜度。

　　雖然這是遞歸算法的一個非常簡單的示例，但我們也有使用遞歸的算法，因為它們比替代解決方案產生更好的結果。

　　遞歸算法 指數時間復雜度 O(2^n)

　　在前面的示例中，遞歸看起來不錯，我們通常可以編寫更少的代碼來解決問題。但是，讓我告訴你，遞歸并不總是最好的解決方案。為了證明這一點，我們將研究斐波那契數列的遞歸實現。

　　功能

　　上述函數是一個斐波那契函數，它啟動兩個遞歸函數，觸發新的函數調用，直到滿足退出條件。解析所有這些函數調用后，結果將冒泡并返回到初始函數。此處的這兩個函數中的每一個都將返回一個值，然后將這些值相加。

　　那么，這種方法有什么問題呢？

　　這種方法的錯誤之處在于，當我們調用它時，該函數會構建一個跨多個分支的嵌套遞歸函數調用樹。

　　這可以在下面的示例圖中看到，因為n = 4。

　　如您所見，我們收到了 9 個函數調用，例如 4 個。如果我們使用基于循環的解決方案來完成它，那么我們只會迭代4次。這不是一個好的解決方案，因為即使對于較小的輸入數字(如 4)，函數調用也有大約 9 次執行。

　　類似地，函數調用呈指數級增長，輸入數字從 4 線性增加到 6，如下所示。

　　如果輸入數字進一步增加，情況會變得更糟。

　　那么這個遞歸函數的時間復雜度是多少呢？

　　這絕對不是O(n)，基于循環的解決方案就是這種情況。我們得到了(9)4次處決，(15)次處決5次，(25)執行6次處決。因此，如果我們僅將提供給函數的數量增加 1，則執行次數將呈指數級增長。它不是線性增長的。我們添加的執行次數似乎隨著n的增大而增長，并且呈指數級增長。

　　因此，這里相對較小的上升需要越來越長的時間。事實上，這個時間尺度的復雜性是指數級的。隨著n的每個增量，我們向這個遞歸樹添加全新的分支，而不僅僅是一個函數調用。此外，每個分支都由其他分支組成。結果，這很快增加到我們的機器無法處理的體積。因此，對于我們已經有一個線性時間復雜度解決方案的問題，這是一個可怕的解決方案。像這樣的遞歸函數說明了它不如基于循環的解決方案。這需要更多的時間。雖然它可能看起來很優雅，但這是一個可怕的解決方案。

　　這是一個指數時間復雜度 O(2^n)。我們確定了函數調用的增長，并且由于其指數，我們可以說該算法具有指數時間復雜性。