C++ recursion | example | My CS Tutorial

Recursion in C++ | Factorial program | Base condition | C++ recursion | Direct recursion vs indirect recursion  | My CS Tutorial

Recursion in c++ | My CS Tutorial

The process in which a function calls itself is known as recursion and the corresponding function is called the recursive function. The popular example to understand the recursion is factorial function.

Factorial function: f(n) = n*f(n-1), base condition: if n<=1 then f(n) = 1. We wil discuss what is base condition and why it is important.

C++ recursion

The C programming language supports recursion, i.e., a function to call itself.
Recursion is the process of repeating items in a self-similar way. In
programming languages, if a program allows you to call a function inside the
same function, then it is called a recursive call of the function.

C++ recursion example: Factorial

C++ program to find the factorial of a given number.

#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

Base condition

In the above program, you can see that I have provided a base condition in the recursive function.

The condition is:

if (n <= 1)
        return 1;
     
The purpose of recursion is to divide the problem into smaller problems till the base condition is reached. For example in the above factorial program I am solving the factorial function f(n) by calling a smaller factorial function f(n-1), this happens repeatedly until the n value reaches base condition(f(1)=1). If you do not define the base condition in the recursive function then you will get stack overflow error.

Direct recursion vs indirect recursion

Direct recursion: When function calls itself, it is called direct recursion, the example we have seen above is a direct recursion example.

Indirect recursion: When function calls another function and that function calls the calling function, then this is called indirect recursion. For example: function A calls function B and Function B calls function A.

Indirect Recursion Example 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


Recursion in C++ programming | Examples of recursion | Recursive functions | C++ recursion | My CS Tutorial

_______________________________________

Please share this post and blog link with your friends.For more programs use this blog.

If you have any problem, please comment in comment box, subscribe this blog for notifications of new post on your email and follow this blog.If you have any method of this program or want to give any suggestion send email on hc78326@gmail.com

Created by-- HARSH CHAUHAN