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 problems 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 problems because the recursive solutions of any problem are easier than 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 a 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:

Code
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 the 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:-

blog banner 1
Fibo

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 time we do 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 the 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 the 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 :-

Liner sum

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.

Frequently Asked Questions

How do you code recursion?

To see code in recursion, you can look up recursive functions in c, recursive functions in python, recursive functions in java, recursive functions in c++ or recursive functions in data structures in general.

What is recursion with an example?

Recursion is the phenomenon in programming where a function, called the recursive function calls itself directly or indirectly based on certain conditions.
Example:
void recursion(int n){
if(n==0) return;
else
recursion(n-1);
}

What is recursion in language?

Recursion in language is the phenomenon of repeating things in a way that seems similar to the parent thing.

What is recursion used for?

Recursion is used for breaking down a complex problem into a simpler problem.

What is recursive thinking?

Recursive thinking is the process of analysing a problem and breaking it down into smaller problems.

What is recursion syntax?

Recursion syntax is the syntax of writing a recursive call which consists of the name of the recursive call and arguments if any.

Conclusion

Now we have done with the recursion in C++. In this tutorial we learned about 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