Recursion in C++

Recursion in C++.
Purpose of recursion.
How recursion works.
Stack Overflow error in recursion.
Types of recursion:
1. Direct recursion.
2. Indirect recursion.
Advantages and Disadvantages of recursion.
Recursion example in C++ program.

1. RECURSION:
Recursion is a process in which a function calls itself.
The function that implements recursion or calls itself is called a Recursive function.
In recursion, the recursive function calls itself repeatedly and keeps on going until an end
condition is met.
To prevent infinite recursion, if else statement (or similar approach) can be used where one
branch makes the recursive call and other doesn't.
Purpose of recursion:
The purpose of recursion is to divide the problem into smaller problems till the base condition is
reached.
How recursion works:
As illustrated in the given diagram. The main function calls a function, funct(). Function funct() in
turn calls itself inside its definition.
Recursion continues until the base condition is met.
If you do not define the base condition in the recursive function, then you will get stack overflow
error.








Explanation:
Factorial function: f(n) = n*f(n-1)
Base condition: if n<=1 then f(n) = 1
As illustrated, the function continues until the base condition is met, then 1 is returned.

2. Stack Overflow error in recursion:
If the base case is not reached or not defined, then the stack overflow problem may arise
The most-common cause of stack overflow is excessively deep or infinite recursion, in which a
function calls itself so many times that the space needed to store the variables and information
associated with each call is more than can fit on the stack
Types of recursion:
Direct recursion: When function calls itself, it is called direct recursion.
Indirect recursion: When function calls another function and that function calls the calling
function, then this is called indirect recursion.
For example: function A calls function B and Function B calls function A.
Advantages of recursion:
 Recursive programs provide compact and clean code.
 A recursive program is a simple way of writing programs
Disadvantages of Recursion:
 The recursive program has greater space requirements than iterative program as all
functions will remain in the stack until the base case is reached.
 It also has greater time requirements because of function calls and returns overhead

3. Example: Recursion for Factorial of a number.










Result (Output):
Input is 5, Output is 120.
Factorial of 5! is 120.