如何在本例中將遞歸轉換爲尾遞歸？

我有這個遞歸函數來添加n個偶數的立方體，我不想把它變成尾遞歸。如何在本例中將遞歸轉換爲尾遞歸？

int sum_even_cubes_rec(int n) { 
if (n < 2) 
    return 0; 
if ((n % 2) == 0) { 
    return (n*n*n + sum_even_cubes_rec(n - 1)); 
} else { 
    return (0 + sum_even_cubes_rec(n - 1)); 
} 
}

這是我寫的，但它是錯誤的，我不知道如何解決它。你能幫我嗎。

int sum_even_cubes_rec2(int n, int acc) { 
if ((n % 2) == 0) { 
    return sum_even_cubes_rec2 (n-1, acc + n*n*n); 
} return acc; 
} 

int sum_even_cubes_helperFunktion(int n) { 
return sum_even_cubes_rec2(n, 0); 
}

來源

2016-11-20 Ema

添加此'如果（N <2）返回0;'作爲一線到代碼和這對'返回sum_even_cubes_rec2第（n-1，ACC）;'作爲最後一行並從你的代碼 –

您的方法是正確的。您已添加acc參數，所以這就是您需要返回的基本情況。

你的代碼的其餘部分幾乎是正確的 - 你需要調整你加什麼acc下一個調用：

int sum_even_cubes_rec2(int n, int acc) { 
    if (n < 2) { 
     return acc; 
    } 
    int nextAcc = (n % 2) == 0 ? acc + n*n*n : acc; 
    return sum_even_cubes_rec2 (n-1, nextAcc); 
}

來源

2016-11-20 12:34:44 dasblinkenlight

中刪除'return acc' ...並且現在你有了尾遞歸，你或者編譯器可以把它變成一個循環（消除遞歸調用）。 –

只要它可以寫成這樣

int sum_even_cubes_rec2(int n) { 
     static int ans = 0; 
     if(n<2){ 
     int tmp =ans; 
     ans =0; 
     return tmp; 
     } 
     ans += ((n%2==0)? n*n*n : 0); 
     return sum_even_cubes_rec2(n-1); 
}

來源

2016-11-20 12:35:56

是的，現在這是一個尾遞歸函數，但它只在您第一次運行它時起作用。從第二次開始，它會返回錯誤的結果，因爲它使用了「靜態」。 – dasblinkenlight

int sum_even_cubes(int n) { 
    int ret =0; 

    if (n < 2) return 0; 

    ret = (n % 2) ? 0: n*n*n; 
    return ret + sum_even_cubes(n-1); 
}

Gcc -O2 -S會將其編譯成（函數參數是%edi;返回值是%eax;目標遞歸環路是.L4）：

sum_even_cubes: 
.LFB0: 
     .cfi_startproc 
     xorl %eax, %eax 
     cmpl $1, %edi 
     jle  .L5 
     .p2align 4,,10 
     .p2align 3 
.L4: 
     xorl %edx, %edx 
     testb $1, %dil 
     jne  .L3 
     movl %edi, %edx 
     imull %edi, %edx 
     imull %edi, %edx 
.L3: 
     subl $1, %edi 
     addl %edx, %eax 
     cmpl $1, %edi 
     jne  .L4 
     rep ret 
.L5: 
     rep ret 
     .cfi_endproc 
.LFE0:

來源

2016-11-20 13:58:59 wildplasser

如何在本例中將遞歸轉換爲尾遞歸？

回答

相關問題