C++ Recursion: Understanding Its Concept and Working

A function in C++ is an important concept that includes the function definition, function declaration, function body, etc. In this article, we will learn about C++ recursion: a recursive function is a particular function that calls itself repeatedly until a certain condition is met. And we will also understand its working in detail. 

Want a Top Software Development Job? Start Here!

Full Stack Developer - MERN StackExplore Program
Want a Top Software Development Job? Start Here!

What Is Recursion in C++?

Recursion is a method in C++ which calls itself directly or indirectly until a suitable condition is met. In this method, we repeatedly call the function within the same function, and it has a base case and a recursive condition. The recursive condition helps in the repetition of code again and again, and the base case helps in the termination of the condition.

If there is no base case in the recursive function, the recursive function will continue to repeat continuously. 

Cpp_Recursion_Example1.

Here, n==0 is the base case that will terminate the iteration of function when n becomes equal to zero. 

return(n-1) is the recursive function that will help in the repetition of code.

Why Do We Need Recursion?

Recursion can be used in almost every problem, but there are some cases where the recursion is actually helpful. It is generally used when dealing with complex problems and problems that form a hierarchical pattern; it solves the original problem via the smaller subproblems.

Cpp_Recursion_Example10

Working of Recursion

Recursion performs a number of repetitive calls to the function from within the function. The recursive condition performs the repeating calls to the function until the base case is met.The base case is present inside the function, and once the condition of the base case is satisfied, it stops the execution.

Let’s understand it with a simple example. 

Cpp_Recursion_Example2.

In the factorial function, we have to perform many repetitive calls to the function. In this example, the recursive condition would be n*factorial(n-1); factorial is the function's name, and the value of n is 5. 

Cpp_Recursion_Example3.

First, in this function, 5 will be multiplied with factorial(5-1), then 4 is passed to the function. Similarly, in the next iteration, 4 is multiplied with factorial(4-1). This will continue till the value of n becomes 1.

Please note that the direction of execution can be -

  • Top to down

       cout<<n;

       function(n-1);

Here, printing of code is done before the recursive call.

  • Bottom to up

       function(n-1);

       cout<<n;

Here, printing is done after the recursive call.

Want a Top Software Development Job? Start Here!

Full Stack Developer - MERN StackExplore Program
Want a Top Software Development Job? Start Here!

Types of Recursion

  • Direct recursion
  • Indirect recursion

Direct recursion: In direct recursion, the function calls itself directly.

Cpp_Recursion_Example4

Indirect recursion: If a function calls itself indirectly from another function, then this type of recursion is called indirect recursion.

Cpp_Recursion_Example11

Examples of Recursion

Now, let us look at some examples of recursion.

1. In the first example, we will find the sum of all the digits up to a particular number, i.e. entered by the user with the help of recursion.

Cpp_Recursion_Example6.

In this example, we will take an input num from the user, and the user will enter the number up to which we have to find the sum. Then, we will pass the variable num to the sum function where the recursion will take place.

Inside the function, there is a condition num!=0, which means the code inside the if block will execute only if the num's value is not equal to zero.

Inside the if block, we are calling the sum function recursively. So, let’s suppose the value of num entered by the user is 5, then inside the function, we will get 5+sum(5-1). Now, we will solve this sum(4), and we will get 4+sum(3), and also we have 5 from the previous equation; therefore, it becomes 5+4+sum(3). Similarly, we will solve sum(3), sum(2) and sum(1), and we will get the sum 5+4+3+2+1.

Here is the output of the above example.

Cpp_Recursion_Example7.

2. In this example, we will print the Fibonacci series using recursion. In the Fibonacci series, each number is the sum of its previous two numbers.

Cpp_Recursion_Example8

In this example, we will take input from the user, and this input would be the number up to which we want to print the series.

We will iterate the for loop from 0 to num, and inside the loop, we will call the fibo function and pass i as an argument. We are passing i as an argument because we want to print the series from 0 to num, so one by one, from 1 to num, all the digits will be passed to the fibo function. 

In the function, there is an if statement in which the condition is n<=1, which means if the value of n is less than or equal to 1, then we will return the value of n. If not, we will call the fibo function recursively and pass the arguments num-1 and num-2 because every digit is the sum of its previous two numbers in the Fibonacci series.

Hereis the output of the above example.

CPP_Recursion_Example9

Want a Top Software Development Job? Start Here!

Full Stack Developer - MERN StackExplore Program
Want a Top Software Development Job? Start Here!

Advantages and Disadvantages of Recursion

Advantages

Disadvantages

Recursion helps in reducing the length of the code.

Recursive functions are a bit slower than non-recursive functions.

It provides a clean and straightforward way to write the code.

It has more significant space requirements than the iterative programs.

It minimizes the calling to the function again and again.

It has a more significant requirement of time due to function calls.

Recursion is preferred in problems like tree traversals and the tower of Hanoi.

It is a bit difficult to understand.

Conclusion

In this tutorial on C++ recursion, we covered topics like  the need for recursion, how it works and types of recursion in C++. You also learned the advantages and disadvantages of recursion, along with some examples.

If you are looking to build a career in software development, check the Post Graduate Program in Full Stack Development by Simplilearn. 

If you have any questions or queries regarding this article on C++ recursion,  put them in the comments section and our experts will ensure they are addressed We’ll help you solve your queries. To learn more about C++ recursion, click on the following link: C++ recursion.

About the Author

Harsh BhardwajHarsh Bhardwaj

Harsh Bhardwaj is currently working as a Research analyst at Simplilearn digital content marketing team. He holds a bachelor’s degree in Computer Science Engineering. He is proficient in C++, Java, CSS, HTML, Bootstrap, and query language like SQL and worked on web development framework like React.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.