如何用Python编写计算Tn=∑(k=1到n)k的尾递归函数

结论 #

你尝试编写的代码不是对应第一个版本的尾递归实现。

原因说明 #

尾递归的核心判定标准是：函数的最后一步操作仅为递归调用自身，调用的返回值会被直接返回，不需要执行任何额外的加减、赋值等运算。
你写的两个版本代码本质逻辑完全一致：递归调用TN(n-1)完成后，还需要执行n + 递归返回值的加法运算，之后才会返回最终结果，因此都属于普通递归，不符合尾递归的要求。

正确尾递归实现 #

尾递归通常需要额外引入累加器参数存储中间计算结果，每次递归直接把当前步的计算结果传入下一次调用，边界条件直接返回累加器即可，示例如下：

def TN(n, accumulator=0):
    if n == 0:
        return accumulator
    # 最后一步仅返回递归调用的结果，无额外运算
    return TN(n - 1, accumulator + n)

补充说明 #

注意Python官方解释器默认没有实现尾递归优化，哪怕写成上述尾递归形式，当递归深度超过默认阈值（约1000）时依然会触发栈溢出错误。如果需要处理大数值的n，更推荐使用循环实现或者直接使用等差数列求和公式n * (n + 1) // 2计算。

内容的提问来源于stack exchange，提问作者user16643263