C++

Recursion In C++ With An Example – Detailed Instructions

Recursion is the process by which a function calls itself, and the associated function is known as a recursive function. The factorial function is a common illustration of recursion.

Factorial function: f(n) = n*f(n-1), with n=1 causing f(n) to equal 1. Don’t worry, we’ll go through what a base condition is and why it’s crucial.

In the diagram below. The factorial function calls itself until it hits the base condition, as I’ve demonstrated.

Example of recursion in C++: Factorial

#include <iostream>
using namespace std;
//Factorial function
int f(int n){
   /* This is called the base condition, it is
    * very important to specify the base condition
    * in recursion, otherwise your program will throw
    * stack overflow error.
    */
   if (n <= 1)
        return 1;
   else 
       return n*f(n-1);
}
int main(){
   int num;
   cout<<"Enter a number: ";
   cin>>num;
   cout<<"Factorial of entered number: "<<f(num);
   return 0;
}

Output:

Enter a number: 5
Factorial of entered number: 120

Basic situation

You can see that I included a base condition in the recursive function in the program above. The circumstance is:

if (n <= 1)
        return 1;

Recursion’s goal is to break the problem down into smaller problems until the basic condition is met. For instance, I am solving the factorial function f(n) in the aforementioned factorial program by invoking the smaller factorial function f(n-1). I do this periodically until the n value satisfies the base condition (f(1)=1) A stack overflow error will occur if the base condition is not defined in the recursive function.

Direct recursion vs indirect recursion

Direct recursion: Direct recursion, as we have just seen in the example above, occurs when a function calls itself.

Indirect recursion: Indirect recursion occurs when a function calls another function, and that function in turn calls the calling function. As an illustration, function A might call function B, and function B might call function A.

Examples of indirect recursion in C++

#include <iostream>
using namespace std;
int fa(int);
int fb(int);
int fa(int n){
   if(n<=1)
      return 1;
   else
      return n*fb(n-1);
}
int fb(int n){
   if(n<=1)
      return 1;
   else
      return n*fa(n-1);
}
int main(){
   int num=5;
   cout<<fa(num);
   return 0;
}

Output:

120

 

Related Articles

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to top button