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