從遞歸進行迭代

Question

我有遞歸函數：

public static int fRek(int n) {   
    if (n <= 0) 
     return 1;    
    else if (n == 1) 
     return 2;  
    else 
     return 3 * fRek(n-2)-3; 
} 

問題：我怎麼能寫在迭代？循環？ 我有這樣的：

public static int fIter(int a) { 
    int b = 1 ; 
     if (a <= 0) return 1;   
     else if (a == 1) return 2; 
     for (int i = 1; i <= a; i = i+2) {    
       b = b * 3;    
       b = b - 3;   
     }   
     return b;  
    } 
} 

但它適用於只是連號：A = 4,6,8，... 爲奇數它不正常工作，我不知道爲什麼

Answer 1

是循環，雖然在這種情況下它不是那麼容易，因爲函數不是尾遞歸。

讓我們先把它轉換成一個尾遞歸函數。爲此，我們傳遞注意到臨時結果如何必須經常去通過最後的功能x => 3*x-3參數：

public static int fRek1(int n, int count) { 
    if (n <= 0) return finalf(1, count); 
    else if (n == 1) return finalf(2, count); 
    else return fRek(n-2, count+1); 
} 
public static int fRek(int n) { return fRek1(n, 0); } 
public static int finalf(int n, int count) { 
    while (count > 0) { 
     n = 3*n-3; 
     count--; 
    } 
    return n; 
} 

現在，你可能會看到如何fRek1轉換上面while循環：只要有塊地方更換遞歸變量n和count得到它們的新值，並將方法體封裝在while (true)中。

Answer 2

你的第二個問題仍然試圖解決這個遞歸。你需要將你的邏輯分解成一個While語句。這裏是一個開始：

int tmp = n 
while (tmp > 1) { 

Insert main logic here 

} 
//Base Cases 
if (tmp == 1) 
    n += 3 

if (tmp <= 0) 
    n += 0 //This does nothing but listing for illustration 

return n; 

Answer 3

對於偶數你的第二個算法是行不通的，因爲，在第一段代碼，該函數返回2如果n == 1：

else if (n == 1) 
    return 2;  

，並在你的第二個算法，如果輸入參數a是奇數，for循環會最終將其減少到1而不是0，因此使用b=1進行計算是不正確的。在a爲奇數的情況下應該使用b=2，在a爲偶數的情況下使用b=1。

此外，你應該使用從i=1的for循環，而a是奇數和i=2而a是偶數。

Answer 4

它適用於偶數的原因是因爲您在函數的開始處對相應的停止條件進行了硬編碼。

看看你的遞歸函數。如果數字是偶數，則會有遞歸調用，直到n == 0;也就是說，直到我們到達這裏：

if (n <= 0) 
    return 1; 

從那裏，我們計算最終結果自下而上。

return 3 * 1 -3; //that's 0 
return 3 * 0 -3; //that's -3 
return 3 * -3 -3; //that's -12 
return 3 * 3 -3; //that's -39 
//...and so on 

在殼體的數量是奇數，我們從2開始，因爲這條線的：

else if (n == 1) 
    return 2; 

從那裏，我們計算最終結果自下而上。

return 3 * 2 -3; //that's 3 
return 3 * 3 -3; //that's 6 
return 3 * 6 -3; //that's 15 
return 3 * 15 -3; //that's 42 
//... and so on  

您的迭代函數像這樣開始。

int b = 1 ; 

也就是說，你要強加一個條件，只有在數量是偶數的情況下才有。相反，你應該測試數字是偶數還是奇數。

if (a % 2 == 0) 
    b = 1;   
else 
    b = 2; 
for (int i = b; i <= a; i = i+2) {  
    //... 
}