Recursion in C++ is a programming technique where a function calls itself in order to solve a problem. It's a powerful and elegant way to solve problems that can be broken down into smaller, similar sub-problems. Recursive functions are divided into two main parts: the base case and the recursive case.
1. Base Case:
The base case is a condition that stops the recursion. Without a base case, the recursion would continue indefinitely, leading to a stack overflow. It's the simplest form of the problem that can be solved directly without further recursive calls.
2. Recursive Case:
The recursive case is where the function calls itself with modified arguments. The goal is to reduce the problem toward the base case. Each recursive call should move closer to a solution. Eventually, the base case is reached, and the recursion stops.
Example:
Factorial Calculation:
We'll create a recursive C++ function to calculate the factorial of a non-negative integer.
#include <iostream>
// Recursive function to calculate the factorial of a number
int factorial(int n) {
// Base case: If n is 0 or 1, return 1
if (n == 0 || n == 1) {
return 1;
} else {
// Recursive case: n! = n * (n-1)!
return n * factorial(n - 1);
}
}
int main() {
int num;
std::cout << "Enter a non-negative integer: ";
std::cin >> num;
if (num < 0) {
std::cout << "Factorial is not defined for negative numbers." << std::endl;
} else {
int result = factorial(num);
std::cout << "Factorial of " << num << " is " << result << std::endl;
}
return 0;
}
In this example:
1. We define a factorial function that calculates the factorial of an integer n.
2. The base case is when n is 0 or 1, in which case, the function returns 1.
3. In the recursive case, the function calls itself with the argument n-1 and multiplies the result by n. This way, it breaks down the problem into smaller sub-problems until it reaches the base case.
4. In the main function, we input a non-negative integer, and if it's negative, we print an error message. Otherwise, we calculate and print the factorial of the input number using the factorial function.
Recursion can be a powerful tool, but it should be used carefully to avoid infinite loops and excessive memory usage. It's important to have a clear base case and ensure that the problem gets closer to the base case with each recursive call.
