Overview

Recursion is a programming technique where a function calls itself to solve a problem. It is typically used to solve problems that can be broken down into smaller, identical sub-problems.

Core Concepts

• Base Case: The condition under which the recursion stops. Without a base case, the function would call itself infinitely.
• Recursive Step: The part of the function where it calls itself with a modified argument, moving closer to the base case.
• Call Stack: The memory structure that tracks active function calls. Each recursive call adds a new “frame” to the stack.
• Tail Recursion: A specific form of recursion where the recursive call is the very last action in the function. Some compilers can optimize this to prevent stack overflows.

Code Examples

// Calculating Factorial: n! = n * (n-1)!
function factorial(n: number): number {
    // 1. Base Case
    if (n <= 1) return 1;
    
    // 2. Recursive Step
    return n * factorial(n - 1);
}

console.log(factorial(5)); // 120

Use Cases

• Tree/Graph Traversal: Navigating folder structures or searching through HTML DOM elements.
• Divide and Conquer: Algorithms like MergeSort and QuickSort.
• Mathematical Sequences: Calculating Fibonacci numbers or factorials.

Gotchas

• Stack Overflow: If the recursion is too deep or the base case is never reached, the program will crash with a “Maximum call stack size exceeded” error.
• Performance: Recursion can be less efficient than iteration due to the overhead of multiple function calls and stack frames.
• Redundant Calculations: Simple recursion (like Fibonacci) can calculate the same value thousands of times. Solution: Use Memoization.

Related Notes

• Functions
• Loops
• Big O Notation