返回斐波那契递归中的节点数

Question

我想编写一个函数，返回斐波那契递归树中的节点数，知道节点数等于计算第 n 个斐波那契数所需的加法数 - 1。

我有一个程序，它返回计算第 n 个斐波那契数的加法次数：

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

def fibR(n):
    #Base case
    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()

如何修改它以返回节点数？我尝试将返回元组的第二个组成部分更改为：

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

但它不起作用。有人可以帮忙吗？预先感谢

Answer 1

n 阶斐波那契树正好有 F(n+2) -1 个节点。 这意味着您可以使用

fibR(i+2)[0]-1

。

def main():
    print('(Fn, additions)')
    for i in range(0, 11):
        print(f"F({i}) = {fibR(i)}")
        print(f"nodes{fibR(i+2)[0]-1}")