Recursion is a programming concept where a function calls itself to solve a problem by breaking it down into smaller, simpler instances of the same problem. Let me explain it using TypeScript code examples.
Let's say we want to calculate the factorial of a number. The factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example, 5! (read as "5 factorial") is calculated as 5 * 4 * 3 * 2 * 1 = 120.
Here's how we can implement a recursive function to calculate the factorial:
function factorial(n: number): number {
// Base case: if n is 0 or 1, return 1
if (n === 0 || n === 1) {
return 1;
}
// Recursive case: multiply n with factorial of (n - 1)
return n * factorial(n - 1);
}
// Calculate the factorial of 5
const result = factorial(5);
console.log(result); // Output: 120In this example, the factorial function takes a number n as input and returns the factorial of that number.
The function first checks for a base case when n is 0 or 1. In this case, it simply returns 1 because 0! and 1! are both equal to 1.
If n is greater than 1, the function calls itself with n-1 as the argument. This is the recursive step where the problem is broken down into a smaller subproblem. The function keeps calling itself with smaller values of n until it reaches the base case.
Once the base case is reached, the function starts returning the results back up the recursive chain. Each returned value is multiplied by the current n and passed up to the previous recursive call until the final result is obtained.
Recursion can be a powerful technique for solving problems that can be divided into smaller subproblems of the same kind. It's important to ensure that recursive functions have appropriate base cases to prevent infinite recursion and that the problem size decreases with each recursive call to avoid stack overflow errors.