Algorithms & Data StructuresFeatured

JavaScript Recursion: Complete Guide with Examples

Master recursion in JavaScript. Learn recursive functions, base cases, call stack, optimization techniques, and common recursive algorithms.

By JavaScriptDoc Team•
recursionalgorithmsfunctionscall stackoptimization

JavaScript Recursion: Complete Guide with Examples

Recursion is a programming technique where a function calls itself to solve a problem by breaking it down into smaller, similar subproblems. It's a powerful concept that can make complex problems easier to solve and code more elegant.

What is Recursion?

Recursion occurs when a function calls itself directly or indirectly. A recursive function must have two essential components:

  1. Base case: A condition that stops the recursion
  2. Recursive case: The function calling itself with modified parameters
// Simple recursive function
function countdown(n) {
  // Base case
  if (n <= 0) {
    console.log('Done!');
    return;
  }

  // Recursive case
  console.log(n);
  countdown(n - 1);
}

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

How Recursion Works

The Call Stack

Understanding the call stack is crucial for understanding recursion.

// Factorial example
function factorial(n) {
  console.log(`factorial(${n}) called`);

  // Base case
  if (n <= 1) {
    console.log(`Returning 1`);
    return 1;
  }

  // Recursive case
  const result = n * factorial(n - 1);
  console.log(`Returning ${n} * factorial(${n - 1}) = ${result}`);
  return result;
}

console.log(factorial(5));
// Call stack visualization:
// factorial(5) -> 5 * factorial(4)
//   factorial(4) -> 4 * factorial(3)
//     factorial(3) -> 3 * factorial(2)
//       factorial(2) -> 2 * factorial(1)
//         factorial(1) -> 1 (base case)
//       returns 2 * 1 = 2
//     returns 3 * 2 = 6
//   returns 4 * 6 = 24
// returns 5 * 24 = 120

Stack Overflow

Recursion without a proper base case or with too many recursive calls can cause a stack overflow.

// This will cause a stack overflow
function infiniteRecursion() {
  return infiniteRecursion(); // No base case!
}

// This might cause stack overflow for large n
function sumToN(n) {
  if (n <= 0) return 0;
  return n + sumToN(n - 1);
}

// sumToN(100000); // RangeError: Maximum call stack size exceeded

// Better: Use iteration for simple cases
function sumToNIterative(n) {
  let sum = 0;
  for (let i = 1; i <= n; i++) {
    sum += i;
  }
  return sum;
}

Common Recursive Patterns

1. Linear Recursion

Each function call makes at most one recursive call.

// Array sum
function arraySum(arr, index = 0) {
  // Base case
  if (index >= arr.length) {
    return 0;
  }

  // Recursive case
  return arr[index] + arraySum(arr, index + 1);
}

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

// String reversal
function reverseString(str) {
  // Base case
  if (str.length <= 1) {
    return str;
  }

  // Recursive case
  return reverseString(str.slice(1)) + str[0];
}

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

// Linked list traversal
class ListNode {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

function printList(node) {
  // Base case
  if (!node) {
    return;
  }

  // Process current node
  console.log(node.value);

  // Recursive case
  printList(node.next);
}

const list = new ListNode(1, new ListNode(2, new ListNode(3)));
printList(list); // 1, 2, 3

2. Binary Recursion

Each function call makes two recursive calls.

// Fibonacci sequence
function fibonacci(n) {
  // Base cases
  if (n <= 1) {
    return n;
  }

  // Recursive case (two calls)
  return fibonacci(n - 1) + fibonacci(n - 2);
}

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

// Binary tree traversal
class TreeNode {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

function inorderTraversal(root, result = []) {
  if (!root) {
    return result;
  }

  inorderTraversal(root.left, result);
  result.push(root.value);
  inorderTraversal(root.right, result);

  return result;
}

const tree = new TreeNode(2, new TreeNode(1), new TreeNode(3));

console.log(inorderTraversal(tree)); // [1, 2, 3]

// Tree height
function treeHeight(root) {
  // Base case
  if (!root) {
    return 0;
  }

  // Recursive case
  const leftHeight = treeHeight(root.left);
  const rightHeight = treeHeight(root.right);

  return 1 + Math.max(leftHeight, rightHeight);
}

3. Multiple Recursion

Each function call makes multiple recursive calls.

// Generate all permutations
function permutations(arr) {
  // Base case
  if (arr.length <= 1) {
    return [arr];
  }

  const result = [];

  for (let i = 0; i < arr.length; i++) {
    const current = arr[i];
    const remaining = arr.slice(0, i).concat(arr.slice(i + 1));
    const perms = permutations(remaining);

    for (const perm of perms) {
      result.push([current, ...perm]);
    }
  }

  return result;
}

console.log(permutations([1, 2, 3]));
// [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

// Generate power set (all subsets)
function powerSet(arr) {
  // Base case
  if (arr.length === 0) {
    return [[]];
  }

  const first = arr[0];
  const rest = arr.slice(1);
  const subsetsWithoutFirst = powerSet(rest);
  const subsetsWithFirst = subsetsWithoutFirst.map((subset) => [
    first,
    ...subset,
  ]);

  return [...subsetsWithoutFirst, ...subsetsWithFirst];
}

console.log(powerSet([1, 2, 3]));
// [[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]

Recursive Algorithms

1. Searching Algorithms

// Binary search (recursive)
function binarySearch(arr, target, left = 0, right = arr.length - 1) {
  // Base case: not found
  if (left > right) {
    return -1;
  }

  const mid = Math.floor((left + right) / 2);

  // Base case: found
  if (arr[mid] === target) {
    return mid;
  }

  // Recursive cases
  if (arr[mid] > target) {
    return binarySearch(arr, target, left, mid - 1);
  } else {
    return binarySearch(arr, target, mid + 1, right);
  }
}

const sortedArray = [1, 3, 5, 7, 9, 11, 13, 15];
console.log(binarySearch(sortedArray, 7)); // 3
console.log(binarySearch(sortedArray, 6)); // -1

// Depth-first search in a graph
function dfs(graph, node, visited = new Set(), result = []) {
  // Mark as visited
  visited.add(node);
  result.push(node);

  // Visit all unvisited neighbors
  for (const neighbor of graph[node] || []) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited, result);
    }
  }

  return result;
}

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D', 'E'],
  C: ['A', 'F'],
  D: ['B'],
  E: ['B', 'F'],
  F: ['C', 'E'],
};

console.log(dfs(graph, 'A')); // ['A', 'B', 'D', 'E', 'F', 'C']

2. Sorting Algorithms

// Merge sort
function mergeSort(arr) {
  // Base case
  if (arr.length <= 1) {
    return arr;
  }

  // Divide
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  // Conquer (recursive calls)
  const sortedLeft = mergeSort(left);
  const sortedRight = mergeSort(right);

  // Combine
  return merge(sortedLeft, sortedRight);
}

function merge(left, right) {
  const result = [];
  let i = 0,
    j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  return result.concat(left.slice(i)).concat(right.slice(j));
}

console.log(mergeSort([64, 34, 25, 12, 22, 11, 90]));
// [11, 12, 22, 25, 34, 64, 90]

// Quick sort
function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pivotIndex = partition(arr, low, high);

    // Recursively sort elements before and after partition
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
  }

  return arr;
}

function partition(arr, low, high) {
  const pivot = arr[high];
  let i = low - 1;

  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }

  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

console.log(quickSort([64, 34, 25, 12, 22, 11, 90]));
// [11, 12, 22, 25, 34, 64, 90]

3. Dynamic Programming with Recursion

// Fibonacci with memoization
function fibonacciMemo() {
  const memo = new Map();

  return function fib(n) {
    // Check memo
    if (memo.has(n)) {
      return memo.get(n);
    }

    // Base cases
    if (n <= 1) {
      return n;
    }

    // Calculate and memoize
    const result = fib(n - 1) + fib(n - 2);
    memo.set(n, result);

    return result;
  };
}

const efficientFib = fibonacciMemo();
console.log(efficientFib(50)); // Calculates quickly

// Longest Common Subsequence
function lcs(str1, str2, i = 0, j = 0, memo = new Map()) {
  // Create key for memoization
  const key = `${i},${j}`;

  // Check memo
  if (memo.has(key)) {
    return memo.get(key);
  }

  // Base case
  if (i === str1.length || j === str2.length) {
    return 0;
  }

  let result;

  // If characters match
  if (str1[i] === str2[j]) {
    result = 1 + lcs(str1, str2, i + 1, j + 1, memo);
  } else {
    // Try both options
    result = Math.max(
      lcs(str1, str2, i + 1, j, memo),
      lcs(str1, str2, i, j + 1, memo)
    );
  }

  memo.set(key, result);
  return result;
}

console.log(lcs('ABCDGH', 'AEDFHR')); // 3 (ADH)

Recursion with Data Structures

1. Tree Operations

// Binary search tree operations
class BSTNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BST {
  constructor() {
    this.root = null;
  }

  insert(value) {
    this.root = this.insertNode(this.root, value);
  }

  insertNode(node, value) {
    // Base case
    if (!node) {
      return new BSTNode(value);
    }

    // Recursive cases
    if (value < node.value) {
      node.left = this.insertNode(node.left, value);
    } else if (value > node.value) {
      node.right = this.insertNode(node.right, value);
    }

    return node;
  }

  search(value) {
    return this.searchNode(this.root, value);
  }

  searchNode(node, value) {
    // Base cases
    if (!node) {
      return false;
    }

    if (node.value === value) {
      return true;
    }

    // Recursive cases
    if (value < node.value) {
      return this.searchNode(node.left, value);
    } else {
      return this.searchNode(node.right, value);
    }
  }

  findMin(node = this.root) {
    // Base case
    if (!node.left) {
      return node.value;
    }

    // Recursive case
    return this.findMin(node.left);
  }

  delete(value) {
    this.root = this.deleteNode(this.root, value);
  }

  deleteNode(node, value) {
    // Base case
    if (!node) {
      return null;
    }

    // Find the node to delete
    if (value < node.value) {
      node.left = this.deleteNode(node.left, value);
    } else if (value > node.value) {
      node.right = this.deleteNode(node.right, value);
    } else {
      // Node found - three cases

      // Case 1: No children
      if (!node.left && !node.right) {
        return null;
      }

      // Case 2: One child
      if (!node.left) {
        return node.right;
      }
      if (!node.right) {
        return node.left;
      }

      // Case 3: Two children
      const minRight = this.findMin(node.right);
      node.value = minRight;
      node.right = this.deleteNode(node.right, minRight);
    }

    return node;
  }
}

// Tree serialization
function serialize(root) {
  if (!root) {
    return 'null';
  }

  return `${root.value},${serialize(root.left)},${serialize(root.right)}`;
}

function deserialize(data) {
  const values = data.split(',');
  let index = 0;

  function buildTree() {
    if (index >= values.length || values[index] === 'null') {
      index++;
      return null;
    }

    const node = new TreeNode(parseInt(values[index++]));
    node.left = buildTree();
    node.right = buildTree();

    return node;
  }

  return buildTree();
}

2. Graph Algorithms

// Detect cycle in directed graph
function hasCycle(graph) {
  const visited = new Set();
  const recursionStack = new Set();

  function dfsHasCycle(node) {
    visited.add(node);
    recursionStack.add(node);

    for (const neighbor of graph[node] || []) {
      if (!visited.has(neighbor)) {
        if (dfsHasCycle(neighbor)) {
          return true;
        }
      } else if (recursionStack.has(neighbor)) {
        return true;
      }
    }

    recursionStack.delete(node);
    return false;
  }

  for (const node in graph) {
    if (!visited.has(node)) {
      if (dfsHasCycle(node)) {
        return true;
      }
    }
  }

  return false;
}

// Topological sort
function topologicalSort(graph) {
  const visited = new Set();
  const stack = [];

  function dfs(node) {
    visited.add(node);

    for (const neighbor of graph[node] || []) {
      if (!visited.has(neighbor)) {
        dfs(neighbor);
      }
    }

    stack.push(node);
  }

  for (const node in graph) {
    if (!visited.has(node)) {
      dfs(node);
    }
  }

  return stack.reverse();
}

const dag = {
  A: ['C'],
  B: ['C', 'D'],
  C: ['E'],
  D: ['F'],
  E: ['F'],
  F: [],
};

console.log(topologicalSort(dag)); // ['B', 'D', 'A', 'C', 'E', 'F']

Optimization Techniques

1. Tail Recursion

Tail recursion occurs when the recursive call is the last operation in the function.

// Not tail recursive
function factorialRegular(n) {
  if (n <= 1) return 1;
  return n * factorialRegular(n - 1); // Multiplication after recursive call
}

// Tail recursive
function factorialTail(n, accumulator = 1) {
  if (n <= 1) return accumulator;
  return factorialTail(n - 1, n * accumulator); // Recursive call is last
}

// Tail recursive sum
function sumTail(arr, index = 0, accumulator = 0) {
  if (index >= arr.length) {
    return accumulator;
  }

  return sumTail(arr, index + 1, accumulator + arr[index]);
}

// Note: JavaScript doesn't optimize tail recursion by default
// But the pattern is still useful for understanding

2. Memoization

Cache results of expensive recursive calls.

// Generic memoization function
function memoize(fn) {
  const cache = new Map();

  return function (...args) {
    const key = JSON.stringify(args);

    if (cache.has(key)) {
      return cache.get(key);
    }

    const result = fn.apply(this, args);
    cache.set(key, result);

    return result;
  };
}

// Memoized recursive functions
const fibonacci = memoize((n) => {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
});

// Grid paths problem
const gridPaths = memoize((m, n) => {
  if (m === 1 || n === 1) return 1;
  return gridPaths(m - 1, n) + gridPaths(m, n - 1);
});

console.log(gridPaths(18, 18)); // Calculates quickly with memoization

3. Converting to Iteration

Sometimes converting recursion to iteration improves performance.

// Recursive approach
function fibRecursive(n) {
  if (n <= 1) return n;
  return fibRecursive(n - 1) + fibRecursive(n - 2);
}

// Iterative approach
function fibIterative(n) {
  if (n <= 1) return n;

  let prev = 0;
  let curr = 1;

  for (let i = 2; i <= n; i++) {
    const next = prev + curr;
    prev = curr;
    curr = next;
  }

  return curr;
}

// Stack-based iteration (simulating recursion)
function inorderIterative(root) {
  const result = [];
  const stack = [];
  let current = root;

  while (current || stack.length > 0) {
    // Go to leftmost node
    while (current) {
      stack.push(current);
      current = current.left;
    }

    // Current is null here
    current = stack.pop();
    result.push(current.value);

    // Visit right subtree
    current = current.right;
  }

  return result;
}

Common Pitfalls and Solutions

1. Missing Base Case

// Wrong: No base case
function badRecursion(n) {
  return badRecursion(n - 1); // Infinite recursion!
}

// Correct: Always have a base case
function goodRecursion(n) {
  if (n <= 0) return; // Base case
  console.log(n);
  goodRecursion(n - 1);
}

2. Incorrect Base Case

// Wrong: Base case doesn't cover all scenarios
function sumArray(arr, index = 0) {
  if (index === arr.length - 1) {
    // Misses empty array
    return arr[index];
  }
  return arr[index] + sumArray(arr, index + 1);
}

// Correct: Handle all edge cases
function sumArrayCorrect(arr, index = 0) {
  if (index >= arr.length) {
    // Handles empty array
    return 0;
  }
  return arr[index] + sumArrayCorrect(arr, index + 1);
}

3. Stack Overflow

// Use iteration for simple linear recursion
function factorial(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

// Or increase stack size (Node.js)
// node --stack-size=10000 script.js

// Or use trampolining for tail recursion
function trampoline(fn) {
  return function (...args) {
    let result = fn(...args);

    while (typeof result === 'function') {
      result = result();
    }

    return result;
  };
}

const factorialTrampoline = trampoline(function factorial(n, acc = 1) {
  if (n <= 1) return acc;
  return () => factorial(n - 1, n * acc);
});

Best Practices

1. Choose the Right Approach

// Use recursion when:
// - Problem has recursive structure (trees, nested data)
// - Divide-and-conquer algorithms
// - Backtracking problems

// Use iteration when:
// - Simple linear processing
// - Performance is critical
// - Stack depth might be an issue

// Example: Tree problems are naturally recursive
function maxDepth(root) {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

// Example: Simple loops are better iterative
function findMax(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) max = arr[i];
  }
  return max;
}

2. Clear Base Cases

// Document base cases clearly
function binarySearch(arr, target, left = 0, right = arr.length - 1) {
  // Base case 1: Element not found
  if (left > right) {
    return -1;
  }

  const mid = Math.floor((left + right) / 2);

  // Base case 2: Element found
  if (arr[mid] === target) {
    return mid;
  }

  // Recursive cases with clear conditions
  if (target < arr[mid]) {
    return binarySearch(arr, target, left, mid - 1);
  } else {
    return binarySearch(arr, target, mid + 1, right);
  }
}

3. Helper Functions

// Public interface with clean API
function reverseLinkedList(head) {
  // Helper function handles the recursion
  function reverseHelper(current, previous = null) {
    // Base case
    if (!current) {
      return previous;
    }

    // Save next node
    const next = current.next;

    // Reverse pointer
    current.next = previous;

    // Recursive call
    return reverseHelper(next, current);
  }

  return reverseHelper(head);
}

// Clean parameters using closure
function permutations(arr) {
  const result = [];

  function generate(current, remaining) {
    if (remaining.length === 0) {
      result.push(current);
      return;
    }

    for (let i = 0; i < remaining.length; i++) {
      generate(
        [...current, remaining[i]],
        [...remaining.slice(0, i), ...remaining.slice(i + 1)]
      );
    }
  }

  generate([], arr);
  return result;
}

Conclusion

Recursion is a powerful programming technique that:

  • Simplifies complex problems by breaking them into smaller subproblems
  • Naturally handles recursive data structures like trees and graphs
  • Enables elegant solutions for algorithms like divide-and-conquer
  • Requires careful consideration of base cases and stack limitations

Key takeaways:

  • Always define clear base cases
  • Consider memoization for overlapping subproblems
  • Be aware of stack limitations
  • Sometimes iteration is more appropriate
  • Practice with tree and graph problems to master recursion

Understanding recursion is essential for:

  • Algorithm interviews
  • Working with hierarchical data
  • Implementing sophisticated algorithms
  • Functional programming paradigms

Master recursion to unlock powerful problem-solving techniques and write more elegant code!