Recursion Fundamentals
Overview
Recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. In code, it simply means a function that calls itself. Recursion is the mathematical foundation for almost all advanced algorithms, including Dynamic Programming, DFS, and Backtracking. While any recursive algorithm can technically be written iteratively (using a Stack), recursion often makes complex branching logic incredibly elegant and readable.
Syntax
If you call `factorial(3)`, it evaluates to `3 * factorial(2)`. The function pauses and calls `factorial(2)`, which evaluates to `2 * factorial(1)`. `factorial(1)` hits the base case and returns 1. The chain then bubbles back up: `2 * 1 = 2`, then `3 * 2 = 6`.
public int factorial(int n) {
// 1. BASE CASE: The condition that STOPS the recursion.
// Without this, the function calls itself forever (Stack Overflow).
if (n <= 1) {
return 1;
}
// 2. RECURSIVE RELATION: Calling itself with a smaller problem.
return n * factorial(n - 1);
}Common Pitfalls
- Forgetting the Base Case or writing a base case that is never reached (e.g., waiting for `n == 0` but `n` is skipping by 2).
- Using recursion for simple mathematical sequences like Fibonacci without Memoization. `fib(50)` will take trillions of years to compute naively because it constantly recalculates the exact same branches.
Interview Tips
- In an interview, NEVER write the recursive logic before writing the Base Case. The Base Case is the anchor.
Real-World Example
Recursion is universally used to traverse hierarchical systems like the DOM tree or file directories.
public void deleteDirectory(File dir) {
// A directory might contain files OR other directories
File[] contents = dir.listFiles();
if (contents != null) {
for (File file : contents) {
// If it's a folder, recursively delete its contents first!
if (file.isDirectory()) {
deleteDirectory(file);
} else {
file.delete(); // Base case: it's just a file
}
}
}
dir.delete(); // Finally, delete the empty directory itself
}