JB TAK FODEGA NHI .... TB TK CHODEGA NHI .... (MAANG)

L1 Introduction of Recursion

When a function call itself again and again still a specific Condition meet that is know as Recursion.

What is recursion? A Function calling itself again and again directly or indirectly is called Recursion, and the function which it calls is called a recursive function, it is used in divide and conquer algorithms/techniques.

Base Case:
A very important point to note in recursion is the base case or stopping condition of recursive calls, if we don’t give a base case then as you saw in the above example so many recursive calls will be made, memory gets wasted and we will not get desired output. So the base condition is very crucial for recursive code.

Stack Overflow!
Think what happens when there is no base case?
Without a base case in recursion, the stack will get filled excessively with recursive calls, once the stack memory exceeds the space allocated by JVM then it will lead to a stack overflow error.
Stack overflow error is a runtime error.

There are two types of recursion direct and indirect:
Direct recursion: Function calling the same function. A function func calls the same function func then it is referred as Direct recursion:

    //Example of direct recursion
    int direct_Func()
    {
        //code….
                           ......
          
      direct_Func();
              
    }

Indirect recursion: Functions calling another functions again and again. A function func1 is called indirect recursion if this func1 calls a new function func2.

    //Example of Indirect recursion
int indirect_func1()
{
	...
	...
	int indirect_func2();

}
int indirect_func2()
{
	...
	...
	int indirect_func1();

}

Advantages and Disadvantages of Recursion

Advantages of recursion:

Code will be short and clean as we just need to define the base case and the recursive case.

To solve such problems which are naturally recursive such as the tower of Hanoi.

Disadvantages of recursion:

Recursive functions are slower than iterative programs.

More complex to analyze the code.

Not efficient in terms of space, as the stack is required.

Not efficient in terms of time complexity too.

Recursion Tree

Notes

Note: Zoom for Better Understanding

Recursion Tree

Code Zone!

Time Complexity:O(4^(m*n))because on every cell we need to try 4 different directions.

Space Complexity:O(m*n) Reason: Maximum Depth of the recursion tree(auxiliary space).