c - 我不知道如何纠正我的尾递归(原本是常规递归)

Question

我被分配了 funct() 并被告知将其转换为尾递归，所以我创建了 funct2()。我使用了另一个堆栈溢出 thread开始并且它有点工作，但它总是一个值(value)。

我 认为 问题是由于 y 值最初为 0，当转到函数的 else 部分时，减去从 0 而不是等于初始 x 的值。但我不确定。

#include <iostream>
#include <stdio.h>
using namespace std;
int funct(int x);
int funct2(int x, int y);

int main() {

    int x = 24;

    printf("%d %d", funct(x), funct2(x, 0));


}

int funct(int x) {

    if (x <= 0){
        return 0;
    }
    else if (x & 0x01){
        return x + funct(x-1);
    }
    else {
        return x - funct(x-1);
    }

}

int funct2(int x, int y) {

    if (x < 0){
        return 0;
    }
    else if (x == 0){
        return y;
    }
    else if (x & 0x01){
        return funct2(x-1, y+x);
    }
    else {
        return funct2(x-1, y-(x-1));
    }

}

感谢任何帮助。谢谢大家!

Answer 1

看看this great explanation .由于您的递归步骤不是关联的，因此您不能只用两个参数实现尾递归。考虑传递三个:

    int tailrec(int x, int k, int acc)
    {
        if (x < 0) {
            return acc;
        }
        if (k & 0x01) {
            return tailrec(x - 1, k + 1, k + acc);
        } else {
            return tailrec(x - 1, k + 1, k - acc);
        }
    }