如何在本例中将递归转换为尾递归？

我有这个递归函数来添加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

如何在本例中将递归转换为尾递归？

回答

相关问题