Understanding Recursive algorithm using FIB 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?

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 :(.