满足指定二阶递推关系的头递归函数转尾递归输出错误求助

开发者阿泽

2026-9-27

正确尾递归实现思路

这类二元递推式的尾递归改造核心是把前两项的计算结果作为入参传递，全程不需要回溯计算，每次递归调用都是函数的最后一步操作，编译器可对栈空间做优化。
先对齐你给出的递推式基础计算结果：

f(0) = 1
f(1) = 2
f(2) = 3*f(1) - f(0) +2 = 6-1+2=7
f(3) =3*f(2)-f(1)+3=21-2+3=22，和你原头递归的运行结果一致。

尾递归C++代码实现

#include <iostream>
using namespace std;

// 尾递归辅助函数
int tailRecurHelper(int target, int currentStep, int prevPrev, int prev) {
    int currentVal = 3 * prev - prevPrev + currentStep;
    if (currentStep == target) {
        return currentVal;
    }
    // 递归调用为最后一步操作，符合尾递归要求
    return tailRecurHelper(target, currentStep + 1, prev, currentVal);
}

int tailRecursion(int n) {
    // 边界条件直接返回
    if (n == 0) return 1;
    if (n == 1) return 2;
    // 从第2步开始递推
    return tailRecurHelper(n, 2, 1, 2);
}

// 原有头递归实现，用于结果对照
int headRecursion(int n) {
    if(n == 0) {
        return 1;
    }
    if (n == 1) {
        return 2;
    }
    return 3 * headRecursion(n - 1) - headRecursion(n - 2) + n;
}

int main(){
    cout << "头递归计算f(3)结果：" << headRecursion(3) << endl;
    cout << "尾递归计算f(3)结果：" << tailRecursion(3) << endl;
    // 可自行增加测试用例验证一致性
    cout << "头递归计算f(5)结果：" << headRecursion(5) << endl;
    cout << "尾递归计算f(5)结果：" << tailRecursion(5) << endl;
    return 0;
}