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

Question

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

Answer 1

你的做法是正确的。您已经添加了 acc 参数，因此这就是您需要为基本情况 return 添加的参数。

您的其余代码几乎是正确的 - 您需要调整为下一次调用添加到 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); 
}

Answer 2

简单的可以这样写

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);
}

Answer 3

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；return 值在 %eax 中；递归循环的目标是 .L4） :

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

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

How to convert recursion to tail recursion in this example?

c

recursion

tail-recursion