Recursion is one of the most important concepts that each programmer should learn thoroughly. In this article, we will study What is Recursion in C++ and how it actually works. We will also learn from some examples which are most frequently asked in the interviews. So, let’s get started!
What Is Recursion?
Recursion is the process of calling the function by itself as its subroutine to solve the complex program. It uses the method of dividing the program into sub-tasks and calling it repeatedly instead of the iterative method which takes lots of time to solve the same problem. Therefore, the function which calls itself is called the recursive function, and the process is called recursion.
The most important thing about the recursion is it should have the base case to terminate the recursion. As the recursive function calls itself continuously, it is always possible that the program goes into an infinite loop. So if we create the terminate base case using the if..else statement, the program will check the base case condition every time and prevent going into the infinite loop.
Learn more about the difference between Recursion and Iteration.
How does Recursion Work?
The function of the recursion approach is to solve the problem effectively in comparison to another problem-solving approach.
The recursion process divides the problem into subtasks as a function and continuously calls the same function again to get one step closer to the final solution. This process continues until we find the final solution to the problem. Each time the part of the solution is found, it is stored in the form of a stack data structure in the memory and at last, popped out to get the final solution.
As we approach the final solution, there is a base condition that should be checked to get out of the recursion process. This base condition is checked using the conditional statement and hence avoids the recursion process getting into the infinite loop. If for any reason the base case fails to work, the program will fall into an infinite loop and we will never reach the solution of the program.
Below is the working of recursion in C++:
void recursion() { ... .. ... recursion(); ... .. ... } int main() { ... .. ... recursion(); ... .. ... }
The figure below shows how recursion works by calling the recursive function again and again.
There are two types of recursive functions i.e. direct recursion and indirect recursion. Direct recursion is when the function calls itself just like we saw in the above program. Indirect recursion is when the function calls another function and then that function calls the calling function.
Why do we need Recursion?
Recursion is a potent programming approach that involves breaking a problem down into smaller, easier subproblems in order to solve it. Recursively solving these subproblems yields a base case. Here are some examples of how recursion is useful in real-world situations and why we need it:
- Code Simplified: Programmers can create code that is elegant and concise by using recursion. This is due to the fact that recursive functions can frequently be written in less code than their iterative equivalents.
- Solves difficult issues: Complex problems that are challenging or impossible to solve using iterative methods benefit greatly from recursion. For instance, it is simple to compute the famed Fibonacci sequence using recursion but challenging to do it iteratively.
- Improving Readability: Compared to iterative functions, recursive functions are frequently simpler to read and comprehend. Recursive functions are more understandable since they can more nearly resemble the issue they are attempting to solve.
Example of a Recursive function in C++ to calculate the factorial of a number:
int factorial(int n) { if (n == 0) { return 1; } else { return n * factorial(n-1); } }
Example of a Recursive function in C++ to calculate the nth Fibonacci number:
int fibonacci(int n) { if (n <= 1) { return n; } else { return fibonacci(n-1) + fibonacci(n-2); } }
Types of Recursion in C++
There are two main types of recursion: direct recursion and indirect recursion.
Direct Recursion
The most typical kind of recursion is direct recursion. A function immediately calls itself when using direct recursion. In other words, a new set of parameters, often generated from the previous call, are passed to the function when it is called. The function keeps calling itself until it encounters a base case, at which point it stops and starts returning results to the calls that came before it in the call stack.
The Fibonacci sequence is implemented in C++ using direct recursion as follows:
int fibonacci(int n) { if (n <= 1) { return n; } else { return fibonacci(n-1) + fibonacci(n-2); } }
Indirect Recursion
A sort of recursion known as indirect recursion occurs when one function calls another, which then calls the original function. In other words, the function uses another function to call itself indirectly.
Additionally, here is a Python implementation of an indirect recursive function:
int b(int n); int a(int n) { if (n == 0) { return 1; } return b(n-1); } int b(int n) { if (n == 0) { return 0; } return a(n-1); }
The ideas of direct recursion and indirect recursion, as discussed in the previous section, are illustrated by these examples. Recursive functions in Python have a very similar syntax to those in other programming languages, where the function calls itself within its own body.
Three Laws of Recursion
Every recursive function should adhere to the three rules of recursion as a fundamental rule. These are what they are:
1) Base Case
Every recursive function needs to have a base case, or the circumstance in which the recursion ends. The base case, then, is the simplest example that the function can solve without recursing, to put it another way.
int factorial(int n) { if (n == 0) { return 1; } else { return n * factorial(n-1); } }
The base case in this illustration is when num is equal to 0. The function returns 1, which ends the recursion when num is 0.
2) Forward Progress
Every recursive function should advance, which implies that with each recursive call, it should get closer to the base case. In other words, the function must move closer to the answer.
int sumOfDigits(int num) { if (num == 0) { return 0; } else { return num % 10 + sumOfDigits(num / 10); } }
Every time this function is called recursively, the size of the number is decreased by eliminating the rightmost digit, coming closer to the base case.
3) Design Rule
The design guideline states that every recursive function should solve a problem by breaking it down into one or more smaller instances of the same problem. In other words, the function should decompose the issue into more manageable subproblems.
int fibonacci(int n) { if (n <= 1) { return n; } else { return fibonacci(n-1) + fibonacci(n-2); } }
The computation of the nth Fibonacci number in this function is split into two smaller computations of the (n-1)th and (n-2)nd Fibonacci numbers. Up until the base case is achieved, this process is repeated.
Top 5 Recursion Examples in C++
Below, we will study some of that recursive programs as an example along with their C++ code. This will help us better learn and understand how recursion works.
1) Fibonacci Series Using Recursion in C++
Fibonacci number series is the sequence of numbers such that each number is the sum of the two preceding ones starting from zero(0) and one(1). Here is the C++ Program:
#include <iostream> using namespace std; int fibonnaci(int x) { if((x==1)||(x==0)) { return(x); }else { return(fibonnaci(x-1)+fibonnaci(x-2)); } } int main() { int x , i=0; cout << "Enter the number of terms of series : "; cin >> x; cout << "\nFibonnaci Series : "; while(i < x) { cout << " " << fibonnaci(i); i++; } return 0; }
Output:
Enter the number of terms of series : 15 Fibonnaci Series : 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
Here in the above program, the "Fibonacci" function is the recursive function that calls itself and finds the Fibonacci series. The time complexity by the recursive Fibonacci program is O(n^2) or exponential.
2) Factorial Program Using Recursion In C++
A Factorial is the product of an integer and all other integers below it. For example, the factorial of 5 (5!) is equal to 5x4x3x2x1 i.e. 120. Here is the complete code:
#include <iostream> using namespace std; int fact(int n); int main() { int n; cout << "Enter a positive integer: "; cin >> n; cout << "Factorial of " << n << " = " << fact(n); return 0; } int fact(int n) { if(n > 1) return n * fact(n - 1); else return 1; }
Output:
Enter an positive integer: 6 Factorial of 6 = 720
Here the recursive function "fact" will take a number as a parameter for which we want to find the factorial. And then recursively call the function until the base condition becomes true which is when the number as a parameter becomes 1.
The time complexity for the recursive factorial program is O(n) because only one loop is executed at a time while finding the factorial of the number using the recursive function. Also, there is no extra space required during recursive calls, and therefore, the space complexity is also O(n).
3) Calculate Number Power Using Recursion
In this C++ program, we will calculate the power of the number using the recursion approach where the base and exponent is taken as input by the user:
#include <iostream> using namespace std; int calculate(int, int); int main() { int base, power, result; cout << "Enter base number: "; cin >> base; cout << "Enter power number(positive integer): "; cin >> power; result = calculate(base, power); cout << base << "^" << power << " = " << result; return 0; } int calculate(int base, int power) { if (power != 0) return (base*calculate(base, power-1)); else return 1; }
Output:
Enter base number: 3 Enter power number(positive integer): 4 3^4 = 81
Here the recursive function "calculate" calls itself again and again with the base condition to check the power until 0 because the exponent is always the positive integer.
The running time complexity for the program to find the power of the number using recursion is O(logn) because every time the recursive function is called, the parameter of the next call is increased by exponential times. Therefore, the time complexity is the function of the log.
4) Reverse A Number Using Recursion
In this program, we will take input from the user as an integer number and reverse it using the recursive function. Here is the complete C++ code:
#include <iostream.h> using namespace std; int reverseNumber(int n) { static temp,sum; if(n>0){ temp = n%10; sum = sum*10 + temp;
reverseNumber(n/10); } else { return sum; } } int main() { int n,reverse; cout<<"Enter number"; cin >> n; reverse = reverseNumber(n); cout << "Reverse of number is" << reverse; return 0; }
Output:
Enter number : 3456 Reverse of number is : 6543
In this program, we will recursively call the "reverseNumber" function with the parameter that the user entered.
The running time complexity of the program is O(log(n)) because every time the function is called recursively, it takes 1/10 of the number as a parameter for the next call. Therefore, the time complexity for reversing the number using the recursive function is O(log(n)).
5) Checking Whether The Number Is Prime using Recursion
A prime number is a number that is divisible only by itself and 1. In this program, we will check whether the given number is a prime number or not. We have the full program here:
#include <bits/stdc++.h> using namespace std; bool isprime(int n, int i = 2) { if (n <= 2) return (n == 2) ? true : false; if (n % i == 0) return false; if (i * i > n) return true; return isprime(n, i + 1); } int main() { int n = 18; if (isprime(n)) cout << "Yes, Number is Prime Number"; else cout << "No, Number is not Prime Number"; return 0; }
Output:
No, Number is not Prime Number
Here, we create the recursive function "isprime" and all it recursively and then check the prime number condition using conditional statements.
The running time complexity of the program to check whether the number is prime or not is O(sqrt(n)) because when we recursively call the function isPrime we check whether it is less than the square root of the given number.
Advantages & Disadvantages
The biggest advantage of Recursion is that it uses less number of code lines and hence the code looks shorter and cleaner. This is an easy approach to solving problems involving data structure and algorithms like graphs and trees. Also, it reduces unnecessary calling of a function and hence, the time complexity is low.
But the limitation is that it consumes a lot of stack space and more time to process the program. One more problem is that if an error is accrued in the program, it is difficult to debug the error in comparison to the iterative program.
The recursion approach is the most important method to solve any program and therefore, there are many popular problem statements that are asked in technical interviews to test your level of understanding of the concept of recursion.
Conclusion
Even though the recursion approach consumes a lot of memory storage because of the use of stack data structure, it is widely used to solve various problem statements to reduce the time complexity and lines of code in the program. Overall, you know more about Recursion in C++ now with some examples to practice.
Check out one such application of the recursive function to reverse the linked list. It is one of the most frequently asked interview questions while clearing the technical rounds and hence, it is recommended to have a strong understanding of the recursion concept.
