Understanding Recursive algorithm using FIB

Question

I am studying for an exam, and I came across this question, I think I got the answer correct, just need some validation.

    Algorithm FIB(n):

    if n = 0 or n = 1
   then f = n
    else
        f = FIB(n-1) + FIB(n-2)
    endif
    return f

If FIB(7) is called how many calls are there to FIB(3)? My answer is 5 because FIB(0) or FIB(1) just returns n, so you do not add them. Then you just add the remainder which I believe is 5. Is this the correct way of looking at this problem or is their a mathematical/formulaic approach?

Answer 1

You should write the recursion tree(the tree is due to the calling of the function) and try to see if there is a recursion for counting it. Your intuition is not correct, try to count FIB(3) in FIB(8) (the remainder is 6 and the answer is 8)

I write it here because i can not do comments :(.