← Previous Next →

Recursion

Recursion is a programming technique where a function calls itself to solve smaller instances of the same problem. It's useful for tasks that can be broken down into similar subtasks.

Illustration of recursion
Illustration of recursion

💡 Key Idea

Each recursive function must have a base case to stop the recursion, preventing infinite loops.

How Recursion Works

  • Recursive Case: The function calls itself with a smaller or simpler input.
  • Base Case: The condition that stops further recursive calls.

Example: Factorial Calculation

The factorial of a number n (written as n!) is the product of all positive integers up to n.

📌 Deep Dive: Factorial with Recursion

JAVASCRIPT
function factorial(n) {
  if (n === 0) return 1;             // Base case
  return n * factorial(n - 1);       // Recursive case
}

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

Why Use Recursion?

  • Simplifies code for problems with repetitive subproblems (e.g., tree traversal, permutations).
  • Helps break down complex problems elegantly.

⚠️ Watch Out for Infinite Recursion

If the base case is missing or incorrect, the function keeps calling itself until the call stack overflows, causing a runtime error.

Common Recursive Patterns

Recursive vs Iterative Approach
ApproachCharacteristics
RecursiveUses function calls, easier to read for some problems, may use more memory
IterativeUses loops, often more efficient, can be harder to conceptualize for nested problems

Tips for Writing Recursive Functions

  • Always define a clear base case.
  • Ensure recursive calls progress toward the base case.
  • Test with small inputs to verify correctness.

📌 Deep Dive: Sum of Array Elements

JAVASCRIPT
function sumArray(arr) {
  if (arr.length === 0) return 0;           // Base case
  return arr[0] + sumArray(arr.slice(1));  // Recursive case
}

console.log(sumArray([1, 2, 3, 4]));  // Output: 10
Output
10

💡 Recursion vs Loops

Recursion replaces loops in many cases but can be less efficient. Some problems are naturally recursive (like tree traversal), while others fit loops better.

← Previous Next →