As a computer science student, if you want to solve advanced problems and projects in the future, the topic where you have to give great focus is “Recursion in C++”.
Recursion is one of the crucial topics that you have to use multiple times when dealing with Data Structures and Algorithms. In this article, we will clarify this concept in a breeze.
TL; DR: Recursion In C++
Aspect | Summary |
Meaning Of Recursion | Recursion is a process where a function calls itself to solve a problem step by step. |
Base (Terminating) Case | Every recursive function must have a base condition to stop execution and avoid infinite calls. |
Recursive Case | The recursive case is the function call that calls itself repetitively, and it is the main driving force of the recursion. |
Key Working Idea | The function keeps calling itself with a smaller value until the base condition is met, then returns the results step by step. |
What Is The Recursion In C++ Programming?
Recursion is a programming process where a function calls itself multiple times to solve a problem. The main idea is to break the big problems into smaller versions so that they can be solved easily.
The function that calls itself in a recursive way is known as the Recursive Function. Sometimes, the function is called from the same function, or sometimes it can be called from any other function.
How Recursion Works In C++?
We have seen that recursion works by calling the same function repetitively. In this process, two essential parts help a lot. They are the Base Case and Recursive Case.
- Base Case: The Base Case is the terminating condition that stops a recursive function from executing in an infinite loop. When the Base Case is true, the Recursion Function stops.
- Recursive Case: This is the Recursive Function Call. This can be identified by the same function name. The recursive case breaks the problem into a smaller one, which will eventually meet the base case at some time.
And to perform all these operations, the Call Stack plays an important role. Each recursive call gets stored in the Call Stack. And when the base case is met, the recursive calls are removed from the call stack by calculating.
In this way, the complete recursion works in C++. The full concept can be further clarified by the above image, where the working of the Call Stack has been shown.
What Are The Different Types Of Recursion In C++?
The C++ Recursion is not of one type. It can be divided into two main categories. This is very important to know for your C++ programming assignment. Let us check their types.
Direct Recursion:
The direct recursion is the recursion where the recursive function is placed in the same function body. That means the function is calling itself, which is the perfect definition we know.
int CodingZap(int n)
{
return n * CodingZap(n + 1); // The Same Function Calling
}
Here, the function CodingZap() is calling itself from the same function body. This is known as the Direct Recursion.
Indirect Recursion:
Indirect Recursion is the opposite of direct recursion. Here, the two functions call themselves in a cyclic order. This type of recursion is rarely used in programming projects and homework.
void Zap()
{
One(); // One() Called From Zap()
}
void One()
{
Zap();// Zap() Called From One()
}
Here, the Function Zap() is calling the Function One(), and the Function One() is calling the Function Zap(). So, both functions are calling cyclically.
Criteria | Direct Recursion | Indirect Recursion |
Function Call | Same | Multiple |
Structure | Simple | Complex |
Dependency | Single | Interdependent |
Readability | Easy | Moderate |
Debugging | Easier | Higher |
How To Implement Recursion In C++? Let's Understand With Example Code.
We have an example program to help you understand what recursion is in C++ in a better way.
In the following example, to know what is meant by recursion in C++, we will see how to find the factorial of a number using recursion.
How to find the factorial of a number using recursion in C++?
Let us see how to find the factorial of a number using recursion with the code below.
#include<iostream>
using namespace std;
// factorial() is a recursive function
int factorial(int n){
if(n == 1) // base condition
return 1;
else
return n*factorial(n-1); // calling the function recursively
}
int main(){
int n, Fact;
cout<<"\t\t\t FACTORIAL USING RECURSION \n\n";
cout<<"Enter the number you want to find the factorial of: ";
cin>>n; //input the number
if(n < 1)
cout<<"Please enter a natural number.";
Fact = factorial(n); // calling the function
cout<<"Factorial of "<<n<<" is "<<Fact; //printing the result
return 0;
}
Steps Of The Program:
- At first, the input number will be taken to find the factorial of.
- Then, we will call the function factorial() to find the factorial for the input number.
- Then, in the function factorial(), we will specify the base condition to terminate.
- When the value of n is equal to one, the recursive call will be terminated.
- To find the factorial of the number, recursively call the function factorial().
- The function will then return the value of the factorial to the main function and print it.
Output:
Suppose the number you want to find the factorial of is 5.
The function factorial() calls itself to find the factorial of (n-1), which is 4 in this case, and returns 5*factorial(4).
The function again invokes itself and finds the factorial of (n-1), which now becomes 3, and returns 4*factorial(3) to the previously called function.
The process is repeated till the value of n becomes 1.
Thus, the result of factorial(1) is returned to factorial(2), which further returns the result to factorial(3) and so on.
Hence, when the function is terminated, we are able to find the factorial of 5, which is 120.
What Are Some Advantages And Disadvantages Of Recursion In C++?
After having a great idea about C++ Recursion, we have to know about the Advantages and disadvantages of C++ recursion. In this section, we will highlight the Pros and Cons of Recursion in C++. Let us check them.
Advantages Of C++ Recursion:
- Recursion makes the code more concise and readable.
- We can easily solve divide-and-conquer problems.
- Recursion is ideal for traversing trees and graphs.
- For Mathematical problems, the recursion improves readability.
Disadvantages Of C++ Recursion:
- It consumes more memory due to the call stack.
- If the input is too large, then it will become slower.
- There can be a StackOverflow issue if the base case is not correct and not met.
- It is very difficult to debug and trace the error in the recursive problems.
Recursion-Based Problems Asked In C++ Assignments:
Recursion-based problems are very common in C++ assignments, as they help students demonstrate their logical clarity on the topic. In a C++ assignment, we can expect to encounter the following common problems.
1. Calculating The Fibonacci Series:
The calculator of the Fibonacci Series is the most obvious question in a C++ assignment. This question tests the understanding of repeated function calls and flow control. Here is the code snippet.
#include <iostream>
using namespace std;
int fibonacci(int n)
{
if (n == 0) // First Base Case
return 0;
if (n == 1) // Second Base Case
return 1;
return fibonacci(n - 1) + fibonacci(n - 2); // Recursion Call
}
2. Product Of Digits Of A Number:
In a C++ Assignment, there will be a question which will ask to perform the Product of Digits or the summation of two values using recursion. The code snippet of the recursion function is the following.
#include <iostream>
using namespace std;
int productOfDigits(int n)
{
if (n == 0) // The Base Case
return 1;
return (n % 10) * productOfDigits(n / 10); // Recursion Call On Product Of Two Digits
}
3. Reverse A Number:
Another good question that you can expect in C++ programming homework is reversing a number or a string. We have developed the code snippet for the recursive call in the following.
#include <iostream>
using namespace std;
void reverseNumber(int n)
{
if (n == 0) // Base Case Of The Function
return;
cout << n % 10; // Printing The Number
reverseNumber(n / 10); // Recursive Call For Previous Digit
}
Use Cases Of C++ Recursion In Homework And Assignments:
Now, you might be thinking, what are some use case fields where you can utilize the Recursion? You will be surprised to know that the list is too long. However, we have brought the following list from where you will get some idea. Let us check it.
- If you are implementing Depth First Search, then recursion is important.
- For working and traversing the Binary Tree, the use of recursion is eminent.
- Problems based on Divide and Conquer should be solved with recursion only.
- If you are doing Mathematical Computation, like factorials and Fibonacci, then recursion is used.
Common Recursion Mistakes In C++ Assignments:
While solving a C++ assignment on Recursion, there are some common mistakes that most students commit. In this section, we will highlight those mistakes so that you can avoid making the same mistakes in your case.
- Sometimes, the student forgets to write the proper base case, which makes the recursion infinite.
- Sometimes, students develop a base case, but it is logically incorrect. Hence, they never occurred.
- Often, students use recursion without reducing the problem size, which increases complexity.
- Sometimes, the recursive call becomes logically incorrect, hence, it gives improper output.
- For even simple loop-based problems as well, students often use recursion as the solution.
Key Takeaways:
- Recursion is the process by which a function calls itself multiple times to divide a large problem.
- Recursion is complete by two main things, the Base Case and the Recursive Case.
- The Base Case helps to terminate the recursion to avoid infinite recursion in the call stack.
- The Recursion Case is the main driving force that divides a large problem into smaller ones.