What is Recursion?
Recursion is a technique in programming where a function calls itself to solve a problem.
Each recursive call works with a smaller part of the original problem until it reaches the base case, where no further calls occur.
Recursive Function Structure
Any recursive function must contain two main elements:
- Base case — condition where the function stops recursive calls.
- Recursive call — calling itself with new arguments.
Example: Factorial
Factorial of number n (n!) is the product of all natural numbers from 1 to n.
function factorial(n: number): number {
if (n === 1) return 1; // Base case
return n * factorial(n - 1); // Recursive call
}
console.log(factorial(5)); // 120
How it Works
Call factorial(5) will unfold like:
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: Array Traversal with Recursion
function printArray(arr: number[], index = 0): void {
if (index >= arr.length) return;
console.log(arr[index]);
printArray(arr, index + 1);
}
printArray([10, 20, 30, 40]);
Recursion vs Iteration
| Characteristic | Recursion | Iteration |
|---|---|---|
| Approach | Function calls itself | Uses loops |
| Memory | Uses Call Stack | More memory efficient |
| Complexity of understanding | Often harder for beginners | Simpler and more visual |
| Flexibility | Good for recursive structures (trees, graphs) | Excellent for sequential operations |
When to Use Recursion?
- Working with trees and graphs (DOM, file system, component tree)
- Parsing nested structures (e.g., HTML or JSON parsing)
- Algorithms: reverse traversal, backtracking, pathfinding
Be Careful with Stack Overflow:
Recursion can lead to stack overflow if there's no base case or the structure is too deeply nested.
Conclusion
- Recursion is a way to solve problems by repeatedly calling a function on itself.
- There must always be a base case for exit.
- Used where problems can be broken into subproblems (especially in data structures).