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.
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.
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.
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.
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.
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
Here, printing of code is done before the recursive call.
- Bottom to up
Here, printing is done after the recursive call.
Types of Recursion
- Direct recursion
- Indirect recursion
Direct recursion: In direct recursion, the function calls itself directly.
Indirect recursion: If a function calls itself indirectly from another function, then this type of recursion is called indirect recursion.
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.
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.
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.
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.
Advantages and Disadvantages of Recursion
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.
It is a bit difficult to understand.
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 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.