Recursion is a programming technique where a function calls itself over again and again with modified arguments until it reaches its base case, where the recursion stops.
It breaks a problem down into smaller, more manageable sub-problems, recursion allows for elegant and better solutions to complex problems.
Recursive Function
A recursive function is a function which is particularly used for recursion where a function calls itself, either directly or indirectly, to address a problem. It must include at least one base case to terminate the recursion and one recursive case where the function invokes itself.
- Base Case − Its a case where recursion stops or ends after reaching that particular condition.
- Recursive Case − Its a case where a function calls itself over again with decremented value until and unless it reaches its base case.
Creating a Recursive Function
The following syntax is used to implement a recursive function in C++ −
function name(param_1, param_2..){<base condition><function body><return statement>}
Here,
- Where, function name(param_1, param_2..) is a function declared as “name” passing with multiple parameters in it as per requirement.
- Now the function body is being divided into three sub-categories : base condition, function body and return statement.
- In base condition we will define its base case, where recursion has to stop or end.
- In the function body, a recursive case will be defined, where we need to call the function over again and again as per requirement.
- At last, the return statement will return the final output of the function.
Calling a Recursive Function
Calling a recursive function is just like calling any other function, where you will use the function’s name and provide the necessary parameters in int main() body.
To call a recursive function, use the following syntax −
func_name(value);
Example of Recursion
Below is an example of a recursion function in C++. Here, we are calculating the factorial of a number using the recursion −
#include <iostream>usingnamespace std;// Recursive Function to Calculate Factorialintfactorial(int num){// Base caseif(num <=1){return1;}// Recursive caseelse{return num *factorial(num -1);}}intmain(){int positive_number;
cout <<"Enter a positive integer: ";
cin >> positive_number;if(positive_number <0){
cout <<"Wrong Input, Factorial is not Defined for Negative Integer"<< endl;}else{
cout <<"Factorial of "<< positive_number <<" is "<<factorial(positive_number)<< endl;}return0;}
Output
Enter a positive integer: 4 (input) Factorial of 4 is 24
Explanation
If take input int positive_number as 4, It will send integer to function name ‘factorial’ as factorial(4)
Initial Call: factorial(4)
This function will check base case (n<=1), as its not satisfying the base case, therefore move forward to recursive case and will compute as “4 * factorial(3)”.
Second call: factorial(3)
This function will again check base case, as its not satisfying it, therefor will again move forward to recursive case , and compute as “3 * factorial(2)”.
Third Call: factorial(2)
Checks base case and computes “2 * factorial(1)”
Fourth call: factorial(1)
Checks base case, now since function satisfying this base case condition thats less than or equal to 1, So it will return 1.
Unwinding the Stack
Now, the recursive calls will start returning: After the 4th call now it will again start from back, returning to the Third Call first.
Return to Third Call: factorial(2)
We already have factorial(1) = 1, therefor factorial(2) will return, “2 * factorial(1)”, thats “2 * 1” , which returns as factorial(2) equals to 2.
Return to Second Call: factorial(3)
Now, factorial(2) is 2, therefore factorial(3) equals to “3 * 2”, thats 6.
Return to Initial Call: factorial(4)
We have factoria(3) which returns 6, therefore, factorial(4) returns “4 * 6 = 24”.
Types of Recursion
Recursion can be categorized into two main types where each with its own sub-categories −
1. Direct Recursion
Direct recursion occurs when a function calls itself directly −
Simple Direct Recursion
The function calls itself with a simpler or smaller instance of the problem. It is used for solving problems like factorial calculation, fibonacci sequence generation, etc.
Tail Recursion
A form of direct recursion where the recursive call is the last operation in the function. It is used for solving accumulative calculations and list processing problems.
intfactorial(int n,int result =1){if(n <=1){return result;}else{returnfactorial(n -1, n * result);// Tail recursive call}}
Head Recursion
The recursive call is made before any other operation in the function. Processing occurs after the recursive call returns. It is used for tree traversals and output generation.
voidprintNumbers(int n){if(n >0){printNumbers(n -1);// Recursive call first
cout << n <<" ";// Processing after recursive call}}
Linear Recursion
Each function call generates exactly one recursive call, forming a linear chain of calls. It is used for simple counting or summing.
intlinearRecursion(int n){if(n <=0){return0;}else{returnlinearRecursion(n -1)+1;// Linear recursive call}}
2. Indirect Recursion
Indirect recursion occurs when a function calls another function, which eventually leads to the original function being called. This involves two or more functions calling each other.
Mutual Recursion
In mutual recursion, two or more functions call each other in a recursive manner, forming a cyclic dependency. It is used for even and odd number classification and grammar parsing.
#include <iostream>usingnamespace std;voideven(int n);voidodd(int n);voideven(int n){if(n ==0){
cout <<"Even"<< endl;}else{odd(n -1);// Calls odd}}voidodd(int n){if(n ==0){
cout <<"Odd"<< endl;}else{even(n -1);// Calls even}}intmain(){even(4);// Outputs: Evenodd(5);// Outputs: Oddreturn0;}
Output
Even Even
Nested Recursion
The nested recursion is a form of indirect recursion where a recursive function makes another recursive call inside its own recursive call. It is used for solving complex mathematical and algorithmic problems.
#include <iostream>usingnamespace std;intnestedRecursion(int n){if(n >100){return n -10;}else{returnnestedRecursion(nestedRecursion(n +11));// Nested recursive calls}}intmain(){
cout <<nestedRecursion(95)<< endl;// Outputs: 105return0;}
Output
91
Advantages of Recursion
- Simplicity and reduced boilerplate code − Recursion helps to simplify solving problems which have a built-in recursive structure, like working with trees or solving combinatorial problems by making it easier to understand and implement.
- Backtracking − Recursion is a great fit for backtracking algorithms, which involve examining all possible solutions to find one which meets certain criteria.
- Effective solutions for divide-and-conquer problems − Recursion works perfectly for Divide-and-conquer algorithms, where problems are broken down into smaller sub parts and are solved one by one. This makes problem solving more efficient and easy.
Recursion Vs. Iteration
Recursion is a method where a function calls itself over again and again with modified arguments until it reaches its base case which stops the recursion. Whereas, an iteration involves using loops (such as for, while or do-while) where it involves repeatedly executing blocks of code until a certain condition is met.
Recursion or Iteration: When to Use?
Recursion
- The problems which can be divided into similar sub-problems or which have natural recursive patterns such as tree traversal or combinational tasks and manageable depth.
- When a user needs simple, cleaner and readable code as it provides clean proper arranged code.
- Examples: Tree and graph traversals, divide-and-conquer algorithms like quicksort and mergesort, and problems involving backtracking like solving mazes or puzzles.
Iteration
- Iterative solutions are generally more efficient in terms of memory and execution time and which involves simple repetition.
- For the problems which require simple looping because iteration is usually more straightforward and efficient.
- Iteration is more stable for problems which require a large number of repetitions, as it doesn’t risk stack overflow.
- Examples: Looping of Array, Vectors and lists, where require simple mathematical computation and repeated execution of a block of code.
Comparison between Recursion and Iteration
| Recursion | Iteration | |
|---|---|---|
| Time Complexity | It can be greater because of its repeated function calls nature. | Comparatively less. |
| Space Complexity | Recursion often uses more Memory because of the call stack. | Uses a fixed amount of Memory. |
| Code Size | In the recursion, the code size is smaller. | Comparatively larger code size. |
| Execution Speed | The execution speed is slow when you use recursion. | Execution speed is more. |
Limitations of Recursion
The following are limitations of recursion −
- Memory Consumption − Each recursive call adds a new frame to the call stack, which can consume a significant amount of memory.
- Stack Overflow Risk − As recursion relies on call stack to manage function calls, Deep recursion can lead to stack overflow as it exceeds the stack size limit.
- Performance Overhead − Recursive functions can be less efficient than iterative ones because they involve overhead from multiple function calls and managing the call stack, which can significantly impact performance, especially with deep recursion.
- Debugging Complexity − Debugging Recursive code can be challenging, especially when dealing with complex recursion or large recursion depths. It needs careful handling of base cases and logic.
- Space Complexity − Due to the call stack in recursion, it can lead to consuming a lot of memory.
