JavaScript Recursion

What is Recursion?

Recursion is when a function calls itself to solve smaller instances of the same problem. Every recursive function needs a base case to stop the recursion and prevent infinite loops.

Recursion is useful for solving problems that have a naturally recursive structure, like tree traversal or mathematical calculations.

// Simple recursion - countdown
function countdown(n) {
  if (n <= 0) {
    console.log("Done!");
    return; // BASE CASE - stop recursion
  }
  console.log(n);
  countdown(n - 1); // RECURSIVE CALL
}

countdown(3);
// Output:
// 3
// 2
// 1
// Done!

// Recursion with return value
function factorial(n) {
  if (n <= 1) {
    return 1; // BASE CASE
  }
  return n * factorial(n - 1); // RECURSIVE CALL
}

console.log(factorial(5)); // 120 (5*4*3*2*1)
console.log(factorial(0)); // 1

Base Cases and Recursive Cases

A recursive function has two parts: the base case that stops recursion, and the recursive case that calls the function again with a simpler problem.

// Sum of array elements
function sumArray(arr, index = 0) {
  // BASE CASE - stop condition
  if (index >= arr.length) {
    return 0;
  }
  
  // RECURSIVE CASE - combine current with rest
  return arr[index] + sumArray(arr, index + 1);
}

console.log(sumArray([1, 2, 3, 4, 5])); // 15

// Find maximum value
function findMax(arr, index = 0) {
  // BASE CASE - single element
  if (index === arr.length - 1) {
    return arr[index];
  }
  
  // RECURSIVE CASE - compare with rest
  const restMax = findMax(arr, index + 1);
  return arr[index] > restMax ? arr[index] : restMax;
}

console.log(findMax([3, 1, 4, 1, 5])); // 5

// String reverse
function reverseString(str) {
  // BASE CASE - empty or single character
  if (str.length <= 1) {
    return str;
  }
  
  // RECURSIVE CASE - last char + reversed rest
  return str[str.length - 1] + reverseString(str.slice(0, -1));
}

console.log(reverseString("hello")); // "olleh"

Common Recursion Patterns

Many problems naturally fit recursive patterns like tree traversal, divide and conquer, and search algorithms.

// Tree traversal (depth-first)
const tree = {
  value: 1,
  left: {
    value: 2,
    left: { value: 4, left: null, right: null },
    right: { value: 5, left: null, right: null }
  },
  right: {
    value: 3,
    left: null,
    right: null
  }
};

function traverse(node) {
  if (node === null) {
    return; // BASE CASE
  }
  console.log(node.value);
  traverse(node.left); // RECURSIVE - left subtree
  traverse(node.right); // RECURSIVE - right subtree
}

traverse(tree); // 1, 2, 4, 5, 3

// Fibonacci sequence
function fibonacci(n) {
  if (n <= 1) {
    return n; // BASE CASE
  }
  return fibonacci(n - 1) + fibonacci(n - 2); // RECURSIVE
}

console.log(fibonacci(10)); // 55

// Binary search
function binarySearch(arr, target, low = 0, high = arr.length - 1) {
  if (low > high) {
    return -1; // BASE CASE - not found
  }
  
  const mid = Math.floor((low + high) / 2);
  if (arr[mid] === target) {
    return mid; // BASE CASE - found
  }
  
  if (arr[mid] < target) {
    return binarySearch(arr, target, mid + 1, high); // RECURSIVE
  } else {
    return binarySearch(arr, target, low, mid - 1); // RECURSIVE
  }
}

console.log(binarySearch([1, 3, 5, 7, 9], 7)); // 3

Understanding the Call Stack

Recursion works by building up a call stack. Each recursive call adds to the stack, then returns values down the stack.

// Visualizing the call stack
function trace(n) {
  console.log("Enter: " + n);
  
  if (n <= 0) {
    console.log("Base case reached");
    return;
  }
  
  trace(n - 1); // Go deeper
  
  console.log("Exit: " + n); // Unwinding
}

trace(3);
// Output:
// Enter: 3
// Enter: 2
// Enter: 1
// Enter: 0
// Base case reached
// Exit: 1
// Exit: 2
// Exit: 3

// Example showing call stack depth
function depth(n = 0) {
  try {
    return 1 + depth(n + 1);
  } catch (e) {
    return n; // Stack overflow caught
  }
}

console.log(depth()); // Stack overflow limit reached

Recursion vs Iteration

Both recursion and iteration can solve the same problems. Choose based on readability and performance.

// Problem: Sum array elements

// Recursive solution - elegant, but uses call stack
function sumRecursive(arr, i = 0) {
  if (i >= arr.length) return 0;
  return arr[i] + sumRecursive(arr, i + 1);
}

// Iterative solution - efficient, uses loop
function sumIterative(arr) {
  let total = 0;
  for (let i = 0; i < arr.length; i++) {
    total += arr[i];
  }
  return total;
}

// Iterative with reduce - functional
function sumFunctional(arr) {
  return arr.reduce((sum, val) => sum + val, 0);
}

const numbers = [1, 2, 3, 4, 5];
console.log(sumRecursive(numbers)); // 15
console.log(sumIterative(numbers)); // 15
console.log(sumFunctional(numbers)); // 15

// When to use each:
// - Recursion: Tree/graph traversal, naturally recursive problems
// - Iteration: Simple loops, when stack depth matters
// - Functional reduce: Array transformations

Tail Call Optimization

Tail call optimization (TCO) allows recursive functions to not grow the call stack if the recursive call is the last operation. JavaScript doesn't always support TCO, but it's good to be aware of.

// Not tail recursive - multiplies after recursive call
function factorialNotTail(n, acc = 1) {
  if (n <= 1) return acc;
  return n * factorialNotTail(n - 1, acc); // Not the last operation
}

// Tail recursive - accumulates result, passes forward
function factorialTail(n, acc = 1) {
  if (n <= 1) return acc; // Last operation returns result
  return factorialTail(n - 1, n * acc); // Tail call
}

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

// Note: JavaScript doesn't always optimize tail calls
// But structuring code this way is good practice

// Example: tail recursive power function
function power(base, exponent, result = 1) {
  if (exponent === 0) return result;
  return power(base, exponent - 1, result * base); // Tail call
}

console.log(power(2, 10)); // 1024

// Practical: tail-recursive list processing
function processItems(items, index = 0, results = []) {
  if (index >= items.length) {
    return results;
  }
  const processed = items[index] * 2;
  results.push(processed);
  return processItems(items, index + 1, results); // Tail call
}

console.log(processItems([1, 2, 3, 4, 5]));
// [2, 4, 6, 8, 10]

Common Mistakes

• Missing base case: Every recursive function must have a base case to stop recursion. Without it, you get infinite recursion and stack overflow.
• Not making progress toward base case: Each recursive call must make progress toward the base case. Otherwise, you'll have infinite recursion.
• Using recursion for simple loops: For simple iterations, use loops instead of recursion. Recursion uses more memory due to call stack.

FAQ

Related Topics