遞歸：一次返回雙倍電話

int f(int n){ 
    if (n==0 || n==1) 
    return 1; 
    else 
    return 2*f(n-1)+2*f(n-2); 
}

如果n = 3，您怎麼看這個步驟？如果只有一個「2 * f（n-1）」，我會知道如何去思考，但有兩個調用。謝謝！遞歸：一次返回雙倍電話

來源

2017-09-16 Oros Tom

好消息是，你不必考慮這一點。電腦足夠聰明，可以爲你思考。如果你坐着一張紙和一支筆，你可以在這裏合理地繪製2-3級遞歸，但這很快就失控了。從這樣的優勢中，沒有什麼可以獲得真正有用的東西。也許你可能想花一些時間研究「通過歸納證明」的純數學概念。一旦你對這個普遍主張感到滿意，這樣的事情將成爲第二天性。 –

我認爲在紙上手工做n = 3或甚至n = 5個初始案例會非常有用。或者，使用調試程序逐步完成，只需在進行時在紙上繪製函數調用。瞭解這裏發生的事情非常重要。 – hyde

它的工作原理與您稱爲兩種不同的功能 - 比如說，2 * g（n-1）+ 2 * h（n-2）'一樣。遞歸函數沒有什麼特別之處。 – molbdnilo

調用圖的n = 3，應是這樣的：

=> 2*f(2)+2*f(1); 
=> 2*[2*f(1)+2*f(0)] + 2*f(1) 
=> 2*[2*1 + 2*1] + 2*f(1) 
=> 8 + 2*1 
=> 10

來源

2017-09-16 12:39:55 nullpointer

OT，Q.E.D.通常放置在演示的*結尾處*;） –

@Bob__沒有太多的話要放在之前:) – nullpointer

如果你把這個在每步操作的一個方面你喜歡的東西：

int f(int n){ 
    return fcont1(n, n < 2); 
} 
int fcont1(int n, int nl2) { 
    if(nl2) { 
     return n; 
    } else { 
     return fcont2(n); 
    } 
} 
int fcont2(int nm1){ 
    return fcont3(n, n-1); 
} 
int fcont3(int n, int nm1){ 
    return fcont4(n, f(nm1)); 
} 
int fcont4(int n, int r1){ 
    return fcont5(r1, n-2); 
} 
int fcont5(int r1, int nm2){ 
    return fcont6(r1, f(nm2)); 
} 
int fcont6(int r1, int r2) { 
    return fcont7(2*r1, r2); 
} 
int fcont7(int dr1, int r2) { 
    return fcont7(dr1, 2*r2); 
} 
int fcont7(int dr1, int dr2) { 
    return dr1+dr2; 
}

這個重寫最後使用了更多的mem因爲C沒有優化尾部調用，但任何執行此操作的語言都與所決定的操作順序完全相同。

來源

2017-09-16 16:13:23 Sylwester

遞歸：一次返回雙倍電話

回答

相關問題