Recursion Fibonacci

#1

Didn’t understood the whole fibonacci concept

#2

We can observe that this implementation does a lot of repeated work (see the following recursion tree). So this is a bad implementation for nth Fibonacci number.

                      fib(5)   
                 /                \
           fib(4)                fib(3)   
         /        \              /       \ 
     fib(3)      fib(2)         fib(2)   fib(1)
    /    \       /    \        /      \

fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/
fib(1) fib(0)
Extra Space: O(n) if we consider the function call stack size, otherwise O(1).