What is recursion in C++?

What is recursion in C++ with Example?

A programming Technique in which a function calls itself is known as recursion in C++. A function that calls itself is called recursive function. The recursion is a powerful technique.


Recursion Example

Factorial Using Recursion in C++

The calculation of factorial of a number is a simple example of a recursive technique.

Suppose the factorial of 5 is to be calculated.
The recursive solution to this problem can be shown as follows:

 recursion in C ++


The Above figure shows that factorial can be calculated by decomposing the problem.

The factorial of 5 can be calculated by multiplying 5 with the factorial of 4.

The factorial of 4 can be calculated by multiplying 4 with the factorial of 3 and so on.

The above procedure can be implemented as follows:

int Factorial(unsigned int n)
{
if(n==0)
return 1;
else
return n*Factorial(n-1);
}

The following table provides a trace of different calls to the Factorial Function:

Factorial of number using recursion


A recursive function must have at least one termination condition that can be satisfied. 

Otherwise, the function will call itself indefinitely. 

The Factorial function has the termination condition n==0 that causes the recursive calls to move back.

programming Example of Recursion

Write a program that inputs a number from the user and calculates its factorial recursively.
+—————————————————-+
#include<iostream.h>
#include<conio.h>
long int fact(int n)
{
if(n==0)
return 1;
else
return n*(n-1);
}
void main()
{
clrscr();
int num;
cout<<“Enter an integer”;
cin>>num;
cout<<“Factorial of <<num<<“is”<<fact(num)”;
getch();
}
+—————————————————-+

Output

Enter an integer 5
Factorial of 5 is 120

Write a program that inputs two integers and calculates the first number raised to the power of the second number recursively.

+—————————————————-+
#include<iostream.h>
#include<conio.h>
int power(int x, int n)
{
if(n<=0)
return 1;
else if(n==1)
return x;
else 
return x*power(x,n-1);
}
void main()
{
clrscr();
int a, b;
cout<<“Enter two integers”;
cin>>a>>b;
cout<<a<<“^”<<b<<“=”<<power(a,b);
getch();
}
+—————————————————-+

Output

Enter two integers 2 5
2^5=32

Also Read:

C++ Program to Insert and Search a Node in Binary Search Tree (BST)