Python双累加器递归函数问题：c系列函数输出异常求助

问题描述 #

我是Python新手，对递归概念不太熟悉。作业要求针对每个基础函数，分别实现后缀为_t（尾递归）、_w（while循环）、_g（生成器）的版本。目前p系列和d系列函数输出均符合预期，但c系列的c_t、c_w、c_g输出异常，只有原函数c(n)结果正确。

完整代码（含错误实现） #

def p(n):
    if n:
        return p(n-1) + 0.02*p(n-1)
    else:
        return 10000

# MUST be implemented with tail recursion
def p_t(n, acc=10000):
    if n == 0:
        return acc
    else:
        return p_t(n - 1, acc * 1.02)

# MUST be implemented with a WHILE LOOP
def p_w(n, acc=10000):
    while n > 0:
        acc = acc * 1.02
        n = n - 1
    return acc

# MUST be implemented with generator
def p_g():
    p = 10000
    yield p
    while True:
       p = p + (0.02 * p)
       yield p

def c(n):
    if n > 1:
        return 9*c(n-1) + 10**(n-1) - c(n-1)
    else:
        return 9

# MUST be implemented with tail recursion
def c_t(n, acc1=9, acc2=0):
    if n == 1:
        return acc1
    else:
        return c_t(n - 1, 9 * acc1 + 10 ** (n - 2) - acc2, acc1)
    
# MUST be implemented with a WHILE LOOP
def c_w(n, acc1=9, acc2=0):
    while n > 1:
        acc1, acc2 = 9 * acc1 + 10 * (n - 2) - acc2, acc1
        n = n - 1
    return acc1

# MUST be implemented with generator
def c_g():
    c = 9
    yield c
    i = 2
    while True:
        c = 9 * c + 10 * (i - 1) - c
        yield c
        i = i + 1

def d(n):
    if n:
        return 3*d(n-1) + 1
    else:
        return 1

# MUST be implemented with tail recursion
def d_t(n, acc=1):
    if n == 0:
        return acc
    else:
        return d_t(n - 1, 3 * acc + 1)

# MUST be implemented with a WHILE LOOP 
def d_w(n, acc=1):
    if n == 0: 
        return 1
    else:
        x = 1
        while x <= n:
            acc = 3 * acc + 1
            x = x + 1
        return acc

# MUST be implemented with generator
def d_g():
    d, n = 1, 1
    yield d
    while True:
        d = 3 * d + 1
        yield d
        n = n + 1

测试用例与输出对比 #

测试代码 #

for i,j in zip(range(1,7),c_g()):
    print(c(i),c_t(i),c_w(i),j)

预期输出 #

9 9 9 9
82 82 82 82
756 756 756 756
7048 7048 7048 7048
66384 66384 66384 66384
631072 631072 631072 631072 

实际错误输出 #

9 9 9 9
82 82 81 82
756 811 810 676
7048 14490 8089 5438
66384 775962 79891 43544
631072 64414531 781220 348402

错误分析与修复方案 #

首先简化原函数c(n)的递推公式：
9*c(n-1) + 10**(n-1) - c(n-1) 等价于 8*c(n-1) + 10^(n-1)，这是修复的核心依据。

1. 尾递归版本c_t修复 #

原实现错误地将10^(n-1)写成10^(n-2)，且参数设计混淆了递推逻辑。重新设计尾递归，跟踪当前的c值和对应的10的幂：

# 修复后的尾递归版本
def c_t(n, current_c=9, ten_power=10):
    if n == 1:
        return current_c
    else:
        # 应用简化后的递推式：8*current_c + ten_power
        return c_t(n - 1, 8 * current_c + ten_power, ten_power * 10)

2. While循环版本c_w修复 #

原实现错误地将10^(n-1)写成10*(n-2)，改为跟踪10的幂并正确应用递推式：

# 修复后的while循环版本
def c_w(n):
    if n == 1:
        return 9
    current_c = 9
    ten_power = 10
    while n > 1:
        current_c = 8 * current_c + ten_power
        ten_power *= 10
        n -= 1
    return current_c

3. 生成器版本c_g修复 #

原实现错误地将10^(i-1)写成10*(i-1)，改为跟踪10的幂并迭代计算：

# 修复后的生成器版本
def c_g():
    current_c = 9
    yield current_c
    ten_power = 10
    while True:
        current_c = 8 * current_c + ten_power
        yield current_c
        ten_power *= 10

验证结果 #

修复后运行测试代码，输出将与预期完全一致。

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