Return the number of nodes in Fibonacci Recursion

Question

I want to write a function that returns the number of nodes in the Fibonacci recursion tree, knowing that the number of nodes equals the number of additions required to compute the n-th Fibonacci number - 1.

I have a program that returns the number of additions to compute the n-th Fibonacci number:

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()

How can i modify it to return the number of nodes? I tried to change the second component of the return tuple to:

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

but it does not work. Can someone help? Thanks in advance

Edit:

Expected Output:

(Fn, additions)
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)

Answer 1

Your forumla fibR(n - 1)[1] + fibR(n - 2)[1] + 1 to calculate the number of nodes is correct. But youve a small mistake in your firb() function. You sometimes returned the wrong value for add. See the code below:

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

def fibR(n):
    #Base case
    global adders
    if n == 0 or n == 1:
        add = n
        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()

#output F(n)=(Fibu value, Number of knots)
F(1) = (1, 1)
F(2) = (1, 2)
F(3) = (2, 4)
F(4) = (3, 7)
F(5) = (5, 12)
F(6) = (8, 20)
F(7) = (13, 33)
F(8) = (21, 54)
F(9) = (34, 88)
F(10) = (55, 143)

Note that the number_of_nodes-1=number_of_additions since the number of additions is the number of branches between the nodes. Since youve given confusing expected outputs heres a picture where you can verify my results by counting the number of nodes or the number of branches yourself.