Recursion in C++
Recursion in a programming language is function calling itself. This article will give a brief of how to use Recursion in C++.
In this article, we will learn about the recursion method in the C++ programming language. We will also understand the characteristic of a recursive function along with a few example programs. So, without further ado, let’s get started!
We will be covering the following sections today:
- What is C++ Recursion?
- Working of Recursion in C++
- Types of Recursion in C++
- Examples of Recursion in C++
- Advantages of Using Recursion in C++
- Disadvantages of Using Recursion in C++
What is C++ Recursion?
Recursion is a C++ method that calls itself repeatedly until a predetermined condition is satisfied.
A recursive function has a base case and a recursive condition, and it repeatedly gets called within the same function directly or indirectly. The base case aids in terminating the condition once it is met, while the recursive condition aids in the repetition of code. The recursive function will continue to loop endlessly if no base case is satisfied.
Let’s understand this approach through a simple C++ code snippet:
void recursion_function() { recursion_function(); //calling self }
Best-suited C++ courses for you
Learn C++ with these high-rated online courses
Working of Recursion in C++
Suppose we have the following piece of code:
void recurse() {
recurse(); //calling self }
int main() { recurse(); }
The following figure will illustrate how recursion works by calling itself over and over repeatedly:
The recursion function will continue looping until a given recursive condition is met. The process of recursion continues until we find the final solution to a given problem. Every time a part of the solution is found, it is stored in the form of a stack data structure in the memory and at the end, it’s popped out to get the final solution.
As we approach the final solution, the base condition is checked using conditional statements to avoid the recursive function from getting stuck in an infinite loop.
Types of Recursion in C++
There are two types of recursive functions in C++:
- Direct Recursion: Here, the function calls itself directly.
void direct_recursion() { ... direct_recursion() { ...}
- Indirect Recursion: Here, the function calls itself from another function indirectly.
void indirect_recursion() { . . . func(); . . . } void func() { . . . indirect_recursion(); . . . }
Examples of Recursion in C++
Let’s look at a few common programs and how they can be written using a recursive function –
Fibonacci Series Using Recursion
The Fibonacci Series is a sequence of numbers where each number is the sum of the two preceding numbers, the first two numbers of the sequence being 0 and 1. A portion of the series is illustrated below:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . .
Now, let’s see how we can display this series using recursion in C++:
#include <iostream> using namespace std;
int fib(int x) { if((x==1)||(x==0)) { return(x); } else { return(fib(x-1) + fib(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 << ” ” << fib(i); i++; } return 0; }
Output:
In the above program, fib() is the recursive function that calls itself and finds the values of the Fibonacci Series.
Factorial Program Using Recursion
The factorial of an integer ‘n’ is actually the product of that number with every whole number less than or equal to ‘n’. For example, the factorial of 6 is denoted by 6! And is given by:
6! = 6 * 5 * 4 * 3 * 2 * 1 = 120
Now, let’s see how we can find the factorial of a given number using recursion in C++:
#include <iostream> using namespace std;
int factorial(int n); int main() { int n; cout << “Enter a positive integer: “; cin >> n; cout << “Factorial of ” << n << ” = ” << factorial(n); return 0; }
int factorial(int n) { if(n > 1) return n * factorial(n – 1); else return 1; }
Output:
In the above program, factorial() is the recursive function that takes an integer as an argument. It then recursively calls itself until the condition becomes true, i.e., n = 1.
Check for a Prime Number Using Recursion
Let us see how we can check if a given number is prime or not using recursion in C++:
#include <iostream> 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; cout << “Enter a positive integer: “; cin >> n; if (isPrime(n)): cout << “Prime Number”; else cout << “Not a Prime Number”; return 0; }
Output:
In the above program, isPrime() is the recursive function that calls itself and checks if the number is prime or not based on the condition using conditional statements.
Advantages of Using Recursion in C++
- Recursion helps reduce unnecessary function calls.
- Using recursion in programs reduces the number of code lines, thereby making the code shorter and cleaner.
- When recursion is used to address problems requiring data structures and algorithms like graphs and trees, it makes the program simpler.
- Recursion aids in reducing the time complexity of a program.
- Recursion is an effective method to define objects that have repeated structural forms.
Disadvantages of Using Recursion in C++
- Recursion programs take more time to process and consume a lot of stack space.
- Recursive methods are slower than non-recursive methods.
- Programs using recursion are difficult to debug when compared to iterative programs.
- Recursion programs are a bit difficult to understand.
Endnotes
The recursion approach is an effective and commonly used method used in C++ and therefore, is a commonly asked concept in technical interviews to test your understanding of the concept. Hope this article helped you grasp the concept and working of recursion in C++. Explore our C++ articles to find out more about the language and consolidate your knowledge of the fundamentals.
This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio
Top Picks & New Arrivals
