Recursion In C++

Explore All About Recursion In C++ With Classic Examples.

In our previous tutorial, we learned more about functions in C++.

Apart from using the functions for breaking down the code into subunits and making the code simpler and readable, functions are useful in various other applications including real-time problems solving, mathematical and statistical computation.

As we develop more complex applications in C++, we come across many requirements so that we need to put several special concepts of C++ to use. Recursion is one such concept.

=> Visit Here For The Complete C++ Tutorials list.

In this tutorial, we will learn more about recursion, where and why it is used along with some classic C++ examples that implement recursion.

What Is Recursion?

Recursion is a process in which a function calls itself. The function that implements recursion or calls itself is called a Recursive function. In recursion, the recursive function calls itself over and over again and keeps on going until an end condition is met.

The below image depicts how Recursion works:

As we see in the above diagram, the main function calls a function, funct(). Function funct() in turn calls itself inside its definition. This is how the recursion works. This process of the function calling itself will continue until we provide a terminating condition which will make it end.

Usually, we provide code branch while implementing recursion such that we provide one condition that will trigger recursion and another to carry out normal execution.

Recursion Base Condition

When recursion is carried out, the solution to the base case or the terminating case is provided and the solutions to bigger problems are built based on the solutions to smaller problems.

Let’s consider a classic example of Recursion, the Factorial notation.

We know that mathematically the factorial of a number n is:

n! = nxn-1x….x0!
given that 0! = 1;

So factorial for n=3 will be 3! = 3×2!

3! = 3x2x1!
3! = 3x2x2x0!
3! = 3x2x1x1 = 6

So programmatically we can express this calculation as follows:

 int factorial(int n){
  if(n <=1)
      return 1;
  else
      return n*factorial(n-1);
}

Thus, as shown above, we have expressed the above calculation of a factorial into a recursive function call. We see that if the number n is less than or equal to 1, we return 1 instead of a recursive call. This is called the base condition/case for the factorial which allows stopping the recursion.

Hence, the base condition basically decides how many times a recursive function should call itself. This means that we can very well calculate the factorial of a larger number by expressing it in terms of smaller numbers until the base class is reached.

Given below is a perfect example to calculate the factorial of a number:

#include <iostream>
#include <string>
using namespace std;

int factorial(int n){
if(n <=1)
  return 1;
else
  return n*factorial(n-1);
}
int main()
 {
   int num,result;
   cout<<"Enter the number whose factorial is to be calculated:"; cin>>num;
   result = factorial(num);
   cout<<num<<"! = "<<result;
 
   return 0;
  }

Output:

Enter the number whose factorial is to be calculated:10
10! = 3628800

In the above example, we implement recursion. We take the number whose factorial is to be found from the standard input and then pass it to the factorial function.

In the factorial function, we have given the base condition as (n<=1). So, when the base case is reached, the function returns. Using this base case, we can calculate factorial of any number greater than 1.

Memory Allocation For The Recursive Call

We know that when a function call is made, the state of the calling function is stored on the stack and when a function call is completed that state is restored back so that the program can continue execution.

When a recursive function call is made, the state or memory for the called function is allocated on top of the state of the calling function and a different copy of local variables is made for every recursive function call.

When the base condition is reached, the function returns to the calling function and the memory is de-allocated and the process continues.

Stack Overflow In Recursion

When recursion continues for an unlimited amount of time, it can result in a stack overflow.

When can recursion continue like this? One situation is when we do not specify the base condition. Another situation is when the base condition is not reached while executing a program.

For Example, we modify the above factorial program and change its base condition.

int factorial(int n){
  if(n ==1000)
    return 1;
  else
    return n*factorial(n-1);
}

In the above code, we have changed the base condition to (n==1000). Now, if we give the number n = 10, we can conclude that the base condition will never reach. This way at some point, the memory on the stack will be exhausted thereby resulting in a stack overflow.

Hence, while designing recursive programs, we need to be careful about the base condition we provide.

Direct Vs Indirect Recursion

So far in recursion, we have seen the function calling itself. This is the direct recursion.

There is another type of recursion i.e. indirect recursion. In this, a function calls another function and then this function calls the calling function. If f1 and f2 are two functions. Then f1 calls f2 and f2, in turn, calls f1. This is an indirect recursion.

Let us revise our factorial program to demonstrate direct recursion.

#include <iostream>
#include <string>
using namespace std;
int factorial_b(int);
int factorial_a(int n){
 if(n <=1)
   return 1;
 else
   return n*factorial_b(n-1);
 }
 int factorial_b(int n){
 if(n <=1)
   return 1;
 else
   return n*factorial_a(n-1);
 }
int main()
{
  int num, result;
  cout<<"Enter the number whose factorial is to be calculated:"; cin>>num;
  result = factorial_a(num);
  cout<<num<<"! = "<<result;
 
  return 0;
}

Output:

Enter the number whose factorial is to be calculated:5
5! = 120

In the above example, we have shown indirect recursion. The main function calls factorial_a. Factorial_a calls factorial_b. In turn factorial_b calls factorial_a. We see that the output of the program is not affected.

Tailed And Non-Tailed Recursion

A tailed recursive function is a recursive function where the last call is executed in the function.

For Example, consider the following function.

void display(int n){
  if(n<=1)
         return;
  cout<<” \t”<<n;
  display(n-1);
}

In the above example, the display is a tailed recursive function such that it is the last function call.

Tailed functions are considered better than non-tailed recursive functions as they can be optimized by the compiler. The reason is that as the tailed recursive call is the last statement in the function, there is no code to be executed after this call.

As a result, saving the current stack frame for the function is not required.

Pros/Cons Of Recursion Over Iterative Programming

Recursive programs provide compact and clean code. A recursive program is a simple way of writing programs. There are some inherent problems like factorial, Fibonacci sequence, towers of Hanoi, tree traversals, etc. which require recursion for solving.

In other words, they are solved efficiently with recursion. They can also be solved with iterative programming using stacks or other data structures but there are chances to become more complex to implement.

Problem-solving powers of recursive as well as iterative programming are the same. However, recursive programs take more memory space as all the function calls need to be stored on the stack until the base case is matched.

Recursive functions also have a time overhead because of too many function calls and return values.

Examples Of Recursion

Next, we will implement some of the examples of recursive programming.

Fibonacci Series

Fibonacci series is the sequence that is given as

0 1 1 2 3 5 8 13……

As shown above, the first two numbers of Fibonacci series are 0 and 1. The next number in the sequence is the sum of the previous two numbers.

Let us implement this series using Recursion.

#include<iostream>
using namespace std;

void fibSeries(int n){
   static int n1=0, n2=1, n3;
   if(n>0){
   n3 = n1 + n2;
   n1 = n2;
   n2 = n3;
   cout<<n3<<" ";
   fibSeries(n-1);
 }
}
int main(){
   int num;
   cout<<"Enter the number of elements for Fibonacci series: "; cin>>num;
cout<<"Fibonacci Series for "<<num<<" numbers: ";
   cout<<"0 "<<"1 ";
   fibSeries(num-2);
   return 0;
}

Output:

Enter the number of elements for Fibonacci series: 10
Fibonacci Series for 10 numbers: 0 1 1 2 3 5 8 13 21 34

In this example, we have used a recursive call to generate the Fibonacci sequence. We see that the first two numbers being constant are directly printed and for the next numbers in the sequence we use a recursive function.

Palindrome

A palindrome number is a number which when read in reverse direction, is the same as read in a left to right direction.

For Example, the number 121 while reading from left to right and right to left reads the same i.e. 121. Hence 121 is a palindrome.

The number 291, when reading from right to left i.e. in reverse order, reads like 192. Hence 291 is not a palindrome.

#include <iostream>
using namespace std;
 
int reverse_digits(int n, int temp)
{
   if (n == 0)
     return temp;
 
     temp = (temp * 10) + (n % 10);
     return reverse_digits(n / 10, temp);
}
 
int main()
{
   int num;
   cout<<"Enter the number to check palindrome:"; cin>>num;
 
   int result = reverse_digits(num, 0);
 
if (result == num)
   cout << "Number "<<num<<" is a palindrome" << endl;
else
   cout << "Number "<<num<<" is not a palindrome"<< endl;
   return 0;
}

Output:

Enter the number to check palindrome:6556
Number 6556 is a palindrome

Screenshot for the same is given below.

In the above program, we read the input number from the standard input. Then we pass this number to a recursive function to reverse the digits of a number. If the reversed digits and the input number are the same then the number is a palindrome.

Conclusion

With this, we have finished with the recursion. In this tutorial, we have studied recursive programming, recursive function, its advantages/disadvantages, along with various examples in detail.

Apart from these examples, recursion is also used in solving some standard problems like traversals (inorder/preorder/postorder), towers of Hanoi, BFS traversal, etc.

=> Visit Here To Learn C++ From Scratch.