Question

why Fibonacci does not have a good performance when it is done recursively? what is a stopping case for recursive functions.?

Answer 1

=> Since Time Complexity of the recursive function is O(2^n) or exponential which is greater than the O(n) Time Complexity in the Iterative approach.

Recursive Code

public static int fibonacciRecursion(int nthNumber) {
        //use recursion
        if (nthNumber == 0) {

            return 0;

        } else if (nthNumber == 1) {

            return 1;
        }   
     return fibonacciRecursion(nthNumber - 1) + fibonacciRecursion(nthNumber - 2);
    }

Space Complexity : The space required is proportional to the maximum depth of the recursion tree, because, that is the maximum number of elements that can be present in the implicit function call stack but for the iterative approach, the amount of space required is the same for fib(6) and fib(100), i.e. as N changes the space/memory used remains the same. Hence its space complexity is O(1) or constant.

Recursion Tree:

=> Stopping Case or Base Case: In the recursive approach, every function call will recursively resolve into n = 1 or n = 0 so we need to return the required value of them to compute the overall function call. Also if the user passes 1 as the function parameter the function should resolve it and return the computed value without getting into the negative value of n in recursive calls.

Drop a comment for any doubt, I would love to resolve it.