目錄
什么是遞歸？
頭遞歸
尾遞歸
樹遞歸
間接遞歸
什么是遞歸？
函數調用自身的過程稱為遞歸，負責的函數稱為遞歸函數。
遞歸類型：
從高層次來看，有四種類型
頭遞歸：
在這里，遞歸函數在檢查基本條件之后和執行任何邏輯之前立即調用自身。
function getsquares(n){
if(n>0){
getsquares(n-1);
console.log(n*n);
return;
}
}
getsquares(3)
登錄后復制
n = 3 的輸出是：1 4 9
如果您注意到了，我們正在打印數字的平方，然后通過將數字減 1 來調用該函數。
因此您將按升序排列所有方塊。
但是，如果您為尾遞歸編寫相同的邏輯，您將按降序獲得輸出。上述代碼的時間復雜度將是 o(n+1) 即 o(n).
尾遞歸：遞歸函數調用自身和結束，即執行完所有邏輯后。
function getsquares(n) {
if (n == 0)
return;
print(n * n);
getsquares(n - 1);
}
getsquares(3)
登錄后復制
n=3 的輸出是： 9 4 1
時間復雜度是o(n+1)即o(n).
樹遞歸：遞歸函數在同一條件下多次調用自身。
function dosomething(n) {
if (n
<p>n=5 的輸出是：8</p>
<p>如果您在圖中注意到，我們以樹狀格式調用 self 函數，這就是為什么我們稱這種類型為<strong>樹遞歸</strong>.</p>
<p>時間復雜度為 <strong>o(2^(n+1)+1)</strong> 即 <strong>o(2^n)</strong>.</p>
登錄后復制
間接遞歸 ：遞歸函數a調用遞歸函數b，函數b調用遞歸函數a。所以，你就明白為什么我們稱之為間接遞歸了。
function doSomethingA(n) {
if (n
<p>n=5 的輸出是：2</p>
<p>說實話，這個例子沒有太多邏輯，我舉這個例子只是為了向你解釋這個概念。</p>
<p>如果您注意到我們正在調用 <strong>dosomethinga()</strong> 并且 dosomethinga 正在調用 <strong>dosomethingb()</strong> 函數，并且進一步 dosomethingb 正在調用 <strong>dosomethinga()</strong> 函數。</p>
<p>這種類型的遞歸調用稱為間接遞歸。</p>
<p><strong>問你的問題：</strong><br><em>嘗試計算間接遞歸的時間復雜度。如果您有任何疑問或者不明白的地方，可以通過寫評論來詢問，我會盡力通過解釋來解決。</em></p>
登錄后復制
