Recursion

What is recursion:
The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function.

For the condition base, is used if… else statement with condition base that is defined and larger value of number can be solved by converting to smaller one till base case is reached.

The solution using recursion is represent problem in terms of one or more smaller problems, and one or more conditions that stop the recursion, for example:

The function sum( ) is called from the main( ), number passed as an argument. Suppose, the value of n inside sum() is 3 initially. During the next function call, 2 is passed to the sum() function. This process continues until n is equal to 0.

When n is equal to 0, the if condition fails and the else part is executed returning the sum of integers ultimately to the main() function.

The output is:

Stack Overflow error:
If the base case is not reached or not defined, then the stack overflow problem may arise, for example:

If sum(10) is called, it will call sum(9), sum(8), sum(7) and so on but the number will never reach 100. So, the base case is not reached. If the memory is exhausted by these functions on the stack, it will cause a stack overflow error.

How memory is allocated to different function calls in recursion?
When any function is called from main(), the memory is allocated to it on the stack. A recursive function calls itself, the memory for a called function is allocated on top of memory allocated to calling function and different copy of local variables is created for each function call. When the base case is reached, the function returns its value to the function by whom it is called and memory is de-allocated and the process continues, for example:

Output:

Advantages and Disadvantages of Recursion
Recursion makes program elegant. However, if performance is vital, use loops instead as recursion is usually much slower.

That being said, recursion is an important concept. It is frequently used in data structure and algorithms. For example, it is common to use recursion in problems such as tree traversal.