Quick Overview
Every recursive call pauses the current frame and stacks a new one holding its own variables. Without a base case the stack keeps growing until the engine refuses, at roughly 10,000 frames.
Recursion is a problem-solving technique where a function solves a smaller sub-instance of the same problem by calling itself.
Every recursive function MUST have two parts:
function factorial(n) {
// Base Case
if (n <= 1) return 1;
// Recursive Step
return n * factorial(n - 1);
}
console.log(factorial(4)); // Output: 24 (4 * 3 * 2 * 1)
Each recursive call allocates a new stack frame in memory storing local variables:
[ factorial(1) -> returns 1 ] ◄── Base Case Reached (Stack Unwinds)
[ factorial(2) -> 2 * 1 ]
[ factorial(3) -> 3 * 2 ]
[ factorial(4) -> 4 * 6 ] ◄── Initial Invocation
Recursive functions consume O(D) auxiliary space on the call stack, where D is the maximum recursion depth.
RangeError: Maximum call stack size exceeded (Stack Overflow!).fib(n) = fib(n-1) + fib(n-2)) runs in horrific O(2^N) exponential time due to repeating identical subproblems. Use memoization or dynamic programming to reduce to O(N)!Mastering recursion is required for trees and backtracking. Next, let's explore Backtracking Patterns!
Big O describes how work grows, not how long it takes. An `O(N^2)` algorithm on 1,000 items does a million steps; the same work at `O(N log N)` does about 10,000.
A dynamic array doubles rather than growing by one, so the expensive copy lands on the 1st, 2nd, 4th and 8th push. Averaged across every push, that is `O(1)` amortised.
A nested loop tests every pair in `O(N^2)`. On sorted data, moving two pointers inward from both ends rules out half the remaining candidates at each step and settles it in one `O(N)` pass.