Recursion

The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called a recursive function. Using a recursive algorithm, certain problems can be solved quite easily. Examples of such problems are Towers of Hanoi (TOH), Inorder/Preorder/Postorder Tree Traversals, DFS of Graph, etc. A recursive function solves a particular problem by calling a copy of itself and solving smaller subproblems of the original problems. Many more recursive calls can be generated as and when required. It is essential to know that we should provide a certain case in order to terminate this recursion process. So we can say that every time the function calls itself with a simpler version of the original problem.

• There are two types of cases in recursion i.e. recursive case and a base case.

• The base case is used to terminate the recursive function when the case turns out to be true.

• Each recursive call makes a new copy of that method in the stack memory.

• Infinite recursion may lead to running out of stack memory.

Need of Recursion

Recursion is an amazing technique with the help of which we can reduce the length of our code and make it easier to read and write. It has certain advantages over the iteration technique which will be discussed later. A task that can be defined with its similar subtask, recursion is one of the best solutions for it. For example; The Factorial of a number.

Working of a Recursive Function

When a recursive function is called, it executes its code until it reaches a point where it needs to solve a smaller version of the same problem. At this point, it calls itself with the smaller problem as input, which starts a new instance of the function on the call stack. Let us see the working of factorial code:

Let us assume we run the above function to find a factorial of 5. The function will execute as:

Step 1. factorial(5) calls factorial(4) with n-1, which is 4.

Step 2. factorial(4) calls factorial(3) with n-1, which is 3.

Step 3. factorial(3) calls factorial(2) with n-1, which is 2.

Step 4. factorial(2) calls factorial(1) with n-1, which is 1.

Step 5. factorial(1) calls factorial(0) with n-1, which is 0.

Step 6. factorial(0) returns 1 to factorial(1).

Step 7. factorial(1) returns 1 *1 to factorial(2).

Step 8. factorial(2) returns 2* 1 to factorial(3).

Step 9. factorial(3) returns 3 *2 to factorial(4).

Step 10. factorial(4) returns 4* 6 to factorial(5).

Step 11. factorial(5) returns 5 * 24, which is 120.

Hence the output will be 120.

Properties of Recursion:

Base case

A base case is a condition where the function returns a value instead of recursive calling itself. We can’t write a recursive function without a base case. Otherwise, it will create an infinite loop and result in a stack overflow error.

Divide and conquer

Recursion involves dividing a problem into smaller sub-problems similar to the original problem. Each sub-problem is solved using the same algorithm as the original problem, and the results are combined to form the final solution.

Function calls itself

Recursion involves calling the same function from within the function itself. This allows for a problem to be broken down into smaller sub-problems that can be solved using the same algorithm.

Stack overflow

One important thing to remember when using recursion is the risk of stack overflow errors. Each recursive call to the function adds a new frame to the stack, and if too many frames are added, the stack will overflow, causing the program to crash.

Memory usage

Recursion can be memory-intensive, as each recursive call creates a new stack frame, which uses memory. If the recursive function is called too many times, it can lead to high memory usage.

Tail recursion

Tail recursion is a special type of recursion where the recursive call is the last statement in the function. This allows some compilers to optimize the code by eliminating the need for new stack frames, reducing memory usage, and improving performance.

Recursion VS Iteration

For problem follow - the list of question