Recursion
A recursive function is a function that calls itself until a base condition is met.
1. Base Case
The condition where recursion stops.
Prevents infinite recursion.
2. Recursive Case
The part where the function calls itself.
Syntax:
return_type function_name(parameters)
{
if(base_condition)
{
return value;
}
else
{
return function_name(modified_parameters);
}
}
Example 1: Factorial Using Recursion
Formula
5! = 5 × 4 × 3 × 2 × 1
C++ Program
#include<iostream>
using namespace std;
int factorial(int n)
{
if(n == 1) // Base Case
{
return 1;
}
else
{
return n * factorial(n - 1); // Recursive Case
}
}
int main()
{
int n;
cout << "Enter a number: ";
cin >> n;
cout << "Factorial = " << factorial(n);
return 0;
}
Output
Enter a number: 5
Factorial = 120
Dry Run of Factorial(5)
factorial(5)
= 5 * factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 * factorial(1)
=5*4*3*2*1
= 120
Example 2: Sum of Natural Numbers Using Recursion
Formula
1 + 2 + 3 + ... + n
C++ Program
#include<iostream>
using namespace std;
int sumNatural(int n)
{
if(n == 1) // Base Case
{
return 1;
}
else
{
return n + sumNatural(n - 1); // Recursive Case
}
}
int main()
{
int n;
cout << "Enter a number: ";
cin >> n;
cout << "Sum = " << sumNatural(n);
return 0;
}
Output
Enter a number: 5
Sum = 15
Dry Run of sumNatural(5)
sumNatural(5)
= 5 + sumNatural(4)
= 5 + 4 + sumNatural(3)
= 5 + 4 + 3 + sumNatural(2)
= 5 + 4 + 3 + 2 + sumNatural(1)
=5+4+3+2+1
= 15
Example 3: x Power y Using Recursion
Formula
x^y = x × x × x ... y times
Example:
2^4 = 2 × 2 × 2 × 2 = 16
C++ Program
#include<iostream>
using namespace std;
int power(int x, int y)
{
if(y == 0) // Base Case
{
return 1;
}
else
{
return x * power(x, y - 1); // Recursive Case
}
}
int main()
{
int x, y;
cout << "Enter x and y: ";
cin >> x >> y;
cout << "Result = " << power(x, y);
return 0;
}
Output
Enter x and y: 2 4
Result = 16
Dry Run of power(2,4)
power(2,4)
= 2 * power(2,3)
= 2 * 2 * power(2,2)
= 2 * 2 * 2 * power(2,1)
= 2 * 2 * 2 * 2 * power(2,0)
=2*2*2*2*1
= 16
Advantages of Recursion
1. Code becomes shorter and cleaner.
2. Reduces complex loop logic.
Disadvantages of Recursion
1. Uses more memory (Function Call Stack).
2. Slower than loops due to repeated function calls.
3. Can cause infinite recursion if base case is missing.
4. May lead to Stack Overflow for very large inputs.