如何将嵌套递归转换为线性递归（最优实现为尾递归）

架构老林

2026-7-25

嵌套递归转线性尾递归实现

问题分析

原函数通过嵌套递归计算，每次求X(n)都要重复计算X(0)到X(n-1)，时间复杂度为O(n²)，且递归深度随n线性增长，容易引发栈溢出。我们可以通过推导递推关系，将其转换为线性时间的尾递归实现，避免重复计算。

递推关系推导

已知递归定义：

X(0)=1; X(n)=n²X(0)+(n-1)²X(1)+...+1²X(n-1)

将X(n)展开为求和式：
X(n) = Σₖ=₀ⁿ⁻¹ (n-k)² X(k)

进一步展开平方项：
X(n) = (n²)ΣX(k) - 2nΣkX(k) + Σk²X(k)（求和范围为k=0到n-1）

我们维护三个累加状态：

sum_X：X(0)到X(k)的和
sum_kX：0*X(0)到k*X(k)的和
sum_k2X：0²*X(0)到k²*X(k)的和

每次计算X(k+1)时，直接用这三个累加值推导，同时更新状态进入下一轮计算，最终实现尾递归。

尾递归实现代码

// 尾递归辅助函数，参数包含当前计算状态
long long x_tail(int k, long long current_X, long long sum_X, long long sum_kX, long long sum_k2X, int n) {
    if (k == n) {
        return current_X;
    }
    int next_k = k + 1;
    // 计算下一个X值
    long long next_X = (long long)next_k * next_k * sum_X - 2LL * next_k * sum_kX + sum_k2X;
    // 更新累加状态
    long long next_sum_X = sum_X + next_X;
    long long next_sum_kX = sum_kX + (long long)next_k * next_X;
    long long next_sum_k2X = sum_k2X + (long long)next_k * next_k * next_X;
    // 尾递归调用
    return x_tail(next_k, next_X, next_sum_X, next_sum_kX, next_sum_k2X, n);
}

// 对外接口函数
long long x(int n) {
    if (n == 0) {
        return 1;
    }
    // 初始状态：k=0，X(0)=1，sum_X=1，sum_kX=0，sum_k2X=0
    return x_tail(0, 1, 1, 0, 0, n);
}