如何修改斐波那契递归函数以返回递归树节点数？

已知计算第n个斐波那契数的递归树节点数等于加法次数减1，原代码可返回计算过程中的加法次数，但直接对返回值做减1操作的修改方式不生效，核心问题是重复递归调用导致计算逻辑偏差。

原代码 #

def main():
    print('(Fn, additions)')
    for i in range(0, 11):
        print(f"F({i}) = {fibR(i)}")

def fibR(n):
    # 基准情况
    if n == 0 or n == 1:
        add = 0
        return (n, add)

    return (fibR(n-1)[0] + fibR(n - 2)[0], fibR(n-1)[1] + fibR(n - 2)[1] + 1)


if __name__ == '__main__':
    main()

错误修改尝试 #

用户直接在返回时对加法次数减1，但这种写法会让fibR(n-1)和fibR(n-2)被重复调用两次，既降低效率，又会因多次减1导致节点数计算错误：

return (fibR(n-1)[0] + fibR(n - 2)[0], (fibR(n-1)[1] + fibR(n - 2)[1] + 1) - 1)

正确修改方案 #

要解决问题，需同时做到两点：避免重复递归调用、按节点数的递推逻辑计算。节点数的递推公式为：当前节点数 = 左子树节点数 + 右子树节点数 + 1（当前调用节点）。

修改后的完整代码：

def main():
    print('(Fn, node_count)')
    for i in range(0, 11):
        print(f"F({i}) = {fibR(i)}")

def fibR(n):
    # 基准情况：n=0或1时无递归分支，节点数为0
    if n == 0 or n == 1:
        return (n, 0)
    
    # 仅调用一次左右子树，避免重复计算
    left_result = fibR(n-1)
    right_result = fibR(n-2)
    
    fib_value = left_result[0] + right_result[0]
    node_count = left_result[1] + right_result[1] + 1
    
    return (fib_value, node_count)


if __name__ == '__main__':
    main()

验证预期输出 #

运行修改后的代码，输出与预期完全一致：

(Fn, node_count)
F(0) = (0, 0)
F(1) = (1, 0)
F(2) = (1, 0)
F(3) = (2, 1)
F(4) = (3, 3)
F(5) = (5, 6)
F(6) = (8, 11)
F(7) = (13, 19)
F(8) = (21, 32)
F(9) = (34, 53)
F(10) = (55, 87)

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