Learning Recursion in C++

Recursion in C++
Recursion in C++

Recursion It is a method used to solve the problems by the instances of smaller problem of the same problem. In other words, we can say that recursion is a function which calls itself directly or indirectly. Recursion is a very popular approach to solve the problems because the recursive solutions of any problem are easier than the iterative solutions. The article highlights the methods of Recursion in C++ Programming.

The problems which are solved by the iterative approach can be solved by recursion.

Working of Recursion:

Basically recursion have only three main steps:-

  • Base Case: The base case is a condition where the recursive function will terminate means it is a stopping condition.
  • Recursive Call: The recursive function will call itself recursively on its smaller problems. During calling this part we have to be more careful and first, we have to check that which is the smaller part of our problem. Then we call recursion on that part. It is an important step in recursion.
  • Small Calculations: We have to do some basic calculations during a recursive call. In some cases, it can be done before a recursive call or after recursive call depending upon the problem given to us.

Relation to PMI:
It is interesting to know that concept of recursion can also be related to the Principle of Mathematical Induction (PMI).

When to prove PMI we also do the three main parts:

  • Base Case: In this concept firstly we do for (X = 0 or X = 1 usually) for making the LHS and RHS true.
  • Induction Hypothesis: We have to assume that it is true of F(k). We don’t have to put a question on this part.
  • Induction Step: Then we make the statement true for the condition (X = K+1) using step 2

Note: Recursion uses a stack to store the recursive calls. If we don’t make the base case, then the condition leads to stack overflow. That’s why we make the base case in recursion.

Let’s understand recursion by Example 1:

include using namespace std; int fact(int n) { if(n==0){ //Base Case

return 1;
}
Return n*fact(n-1); // Recursive call with small calculations
}
Int main() {
int num;
Cin >> num;
Cout << fact(num);
Return 0;
}
Output: 120 // For num = 5

Explanation of the code:
Let’s understand the example firstly we go to the main part of the code. In that, we have declared a num variable with data the data type integer. Then we call the recursion part. Ongoing to the recursive function we are taking a num which sore the value given by us.
There we made a base case which is a clear notation to terminate our recursive call. As recursion calls 0 it returns 1 to code. Then we have done some small calculations and also recursive call.

We can understand it by diagram also:

Example 2: – Fibonacci Series
Int fibo ( int n) {
If( n == 0 || n == 1 ) { // Base Case
return n;
}
int a = fibo (n-1 ); //Recursive Call
int b = fibo (n-2); //Recursive Call
return a+b; // Small Calculations
}
Explanation:- As we all are aware of Fibonacci series which is adding of continuous number. (0,1,1,2,3,5,8,13,21,……)
In code first, we check that the number we entered is zero or one. If yes then we simply return the value of n. if the value is not zero or one then we recursively call the Fibonacci with the values n-1 and n-2.


Let’s understand by the diagram:-

Recursion with arrays:
In arrays generally, we do our problems by using recursion it makes our problem much easier. We will include all the main three parts in recursion with arrays also. In arrays most of the times we do like this, first we make the base case. While calling recursive call we keep the first element with us and call recursion on the rest array. After this index 1 to n will be done by recursion and most important talk is here that we never question the recursion how it has done the part. We will dry run our code. After or before we can do our small calculations depending upon question need. This is the general way to approach the arrays.

Example:

int sum (int input[], int n) {
if(n == 0){ //Base Case
return 0;
}
int ssa = input[0] + sum(input+1, n-1); // Small calculation with recursive call
return ssa; }
Input :- 3
1 2 3
Output:- 5

In above example we did the same approach we discussed earlier, we call on the array by keeping the first element with us and at last we attach the element.

Note: – One more thing to notice in arrays is that if we don’t pass the size of the array in function, we can’t find the size of the input array. Suppose we don’t give the size of the array then how we can stop the recursive calls. So when you are working on arrays pass the size also with the input array.

Understand with the help of diagram :-

Recursion with Strings: –

As we know strings also behave like arrays so the approach is also same but here comes a little change that in array we stop writing numbers when we want. In strings it also happens but as we done with the input automatically a null character (\0) will append. Which denotes that you have ended the string.

In strings you must take care of this.

Example:

void replaceCharacter(char input[], char c1, char c2) {
if(input[0] == ‘\0’){ //Base Case
return ;
}
if(input[0] == c1){ //Small Calculation
input[0] = c2;
}
replaceCharacter(input+1,c1,c2); //Recursive call
}

In above code just see the base case there clearly written that when we find the null character we just simply return. If we find the required character on index zero, then we just replace that char with the desired one. At the end we pass the remaining string is given to recursive calls.

Recursion and Iteration:

  • In recursion, function calls itself but in iteration set of instructions will be called.
  • Infinite recursion can trash the system but infinite iteration uses CPU cycles repeatedly.
  • Recursion makes the code small but iteration makes the code longer.
  • While calling the recursion we use the stack to store the recursive calls but in the iterative case, we don’t use the stacks.
  • Recursion applied to the functions but the iteration can be used in loops.

Advantages of Recursion:

  • Recursion can reduce time complexity. As in Fibonacci series, the iterative approach takes more than recursion. We can also reduce the time of recursion by memoisation.
  • Recursion makes the code clear and reduces the length of code and it is a good choice to debug your code.
  • Recursion performs better in the tree traversal. In simple words, a tree is a collection of objects linked to one another. If you look tree recursively it looks very simple. It is more beneficial when you use the pre-order tree traversal.
Example of tree traversal

Disadvantages of Recursion:

  • Recursion uses more memory because the function has to add each call and keep its value there until the last call will be done. In this way, it takes more memory than the iterative approach.
  • Recursion takes a lot of stack space, usually not considered when the program is small and running on a PC.
  • It is slower than the iterative approach.

Conclusion

Now we have done with the recursion in C++. In this tutorial we learnt about the recursion, working with recursion, recursion with an array, recursion with string, advantages and disadvantages of recursion and also explained some examples on recursion in detail. Apart from the given examples recursion is also used to solve problems of traversals, Tower of Hanoi, linked list, BST tree etc.

To read about Recursion in C++, click here.

By Akhil Sharma