Recursion - Complete Guide for Beginners

Recursion is a programming technique where a function calls itself to solve smaller instances of the same problem. This guide covers recursion fundamentals and common patterns.

What is Recursion? #

Recursion occurs when a function calls itself to break down a problem into smaller, more manageable subproblems.

Key Components:

Base case - Stopping condition
Recursive case - Function calls itself with modified parameters

Basic Recursion Example #

Countdown #

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 #

Call Stack #

function factorial(n) {
  if (n === 0) return 1;
  return n * factorial(n - 1);
}

factorial(3);

Call Stack Visualization:

factorial(3)
  3 * factorial(2)
        2 * factorial(1)
              1 * factorial(0)
                    return 1
              return 1 * 1 = 1
        return 2 * 1 = 2
  return 3 * 2 = 6

Classic Recursion Problems #

Factorial #

function factorial(n) {
  if (n === 0 || n === 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

console.log(factorial(5));  // 120
// 5! = 5 × 4 × 3 × 2 × 1 = 120

Fibonacci #

function fibonacci(n) {
  if (n <= 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(6));  // 8
// Sequence: 0, 1, 1, 2, 3, 5, 8

Sum of Array #

function sumArray(arr) {
  if (arr.length === 0) {
    return 0;
  }
  return arr[0] + sumArray(arr.slice(1));
}

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

Power #

function power(base, exponent) {
  if (exponent === 0) {
    return 1;
  }
  return base * power(base, exponent - 1);
}

console.log(power(2, 5));  // 32

Reverse String #

function reverseString(str) {
  if (str === "") {
    return "";
  }
  return reverseString(str.slice(1)) + str[0];
}

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

Array and String Recursion #

Count Occurrences #

function countOccurrences(arr, target) {
  if (arr.length === 0) {
    return 0;
  }

  const count = arr[0] === target ? 1 : 0;
  return count + countOccurrences(arr.slice(1), target);
}

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

Flatten Array #

function flatten(arr) {
  let result = [];

  for (const item of arr) {
    if (Array.isArray(item)) {
      result = result.concat(flatten(item));
    } else {
      result.push(item);
    }
  }

  return result;
}

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

Palindrome Check #

function isPalindrome(str) {
  if (str.length <= 1) {
    return true;
  }

  if (str[0] !== str[str.length - 1]) {
    return false;
  }

  return isPalindrome(str.slice(1, -1));
}

console.log(isPalindrome("racecar"));  // true
console.log(isPalindrome("hello"));    // false

Tree Recursion #

Binary Tree Traversal #

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

// Inorder: Left -> Root -> Right
function inorder(root) {
  if (!root) return;

  inorder(root.left);
  console.log(root.val);
  inorder(root.right);
}

// Preorder: Root -> Left -> Right
function preorder(root) {
  if (!root) return;

  console.log(root.val);
  preorder(root.left);
  preorder(root.right);
}

// Postorder: Left -> Right -> Root
function postorder(root) {
  if (!root) return;

  postorder(root.left);
  postorder(root.right);
  console.log(root.val);
}

Tree Height #

function maxDepth(root) {
  if (!root) {
    return 0;
  }

  const leftDepth = maxDepth(root.left);
  const rightDepth = maxDepth(root.right);

  return Math.max(leftDepth, rightDepth) + 1;
}

Tree Sum #

function sumTree(root) {
  if (!root) {
    return 0;
  }

  return root.val + sumTree(root.left) + sumTree(root.right);
}

Divide and Conquer #

Binary Search #

function binarySearch(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) {
    return -1;
  }

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

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

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

Merge Sort #

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

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

  return merge(left, right);
}

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([5, 2, 8, 1, 9]));
// [1, 2, 5, 8, 9]

Quick Sort #

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const pivot = arr[Math.floor(arr.length / 2)];
  const left = arr.filter(x => x < pivot);
  const middle = arr.filter(x => x === pivot);
  const right = arr.filter(x => x > pivot);

  return [...quickSort(left), ...middle, ...quickSort(right)];
}

console.log(quickSort([5, 2, 8, 1, 9]));
// [1, 2, 5, 8, 9]

Backtracking #

Generate Permutations #

function permutations(arr) {
  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 Subsets #

function subsets(nums) {
  const result = [];

  function backtrack(start, current) {
    result.push([...current]);

    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);
      backtrack(i + 1, current);
      current.pop();
    }
  }

  backtrack(0, []);
  return result;
}

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

N-Queens Problem #

function solveNQueens(n) {
  const result = [];
  const board = Array(n).fill(0).map(() => Array(n).fill('.'));

  function isValid(row, col) {
    // Check column
    for (let i = 0; i < row; i++) {
      if (board[i][col] === 'Q') return false;
    }

    // Check diagonal
    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (board[i][j] === 'Q') return false;
    }

    // Check anti-diagonal
    for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
      if (board[i][j] === 'Q') return false;
    }

    return true;
  }

  function backtrack(row) {
    if (row === n) {
      result.push(board.map(r => r.join('')));
      return;
    }

    for (let col = 0; col < n; col++) {
      if (isValid(row, col)) {
        board[row][col] = 'Q';
        backtrack(row + 1);
        board[row][col] = '.';
      }
    }
  }

  backtrack(0);
  return result;
}

console.log(solveNQueens(4));

Memoization #

Optimize recursive functions by caching results:

// Without memoization - Exponential time
function fibSlow(n) {
  if (n <= 1) return n;
  return fibSlow(n - 1) + fibSlow(n - 2);
}

// With memoization - Linear time
function fib(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;

  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}

console.log(fib(50));  // Fast
// console.log(fibSlow(50));  // Very slow!

Memoization Pattern #

function memoize(fn) {
  const cache = {};

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

    if (key in cache) {
      return cache[key];
    }

    const result = fn.apply(this, args);
    cache[key] = result;
    return result;
  };
}

// Usage
const fibMemoized = memoize(function(n) {
  if (n <= 1) return n;
  return fibMemoized(n - 1) + fibMemoized(n - 2);
});

Recursion vs Iteration #

Advantages of Recursion #

Cleaner code - More readable for some problems
Natural fit - Trees, graphs, divide-and-conquer
Elegant solutions - Less code for complex problems

Disadvantages of Recursion #

Stack overflow - Deep recursion uses stack space
Performance - Function call overhead
Memory - Each call uses memory

Converting Recursion to Iteration #

Recursive:

function factorial(n) {
  if (n === 0) return 1;
  return n * factorial(n - 1);
}

Iterative:

function factorial(n) {
  let result = 1;
  for (let i = 1; i <= n; i++) {
    result *= i;
  }
  return result;
}

Common Recursion Patterns #

Linear Recursion #

Single recursive call:

function sum(n) {
  if (n === 0) return 0;
  return n + sum(n - 1);
}

Binary Recursion #

Two recursive calls:

function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

Multiple Recursion #

More than two recursive calls:

function treeSum(root) {
  if (!root) return 0;
  return root.val + treeSum(root.left) + treeSum(root.right);
}

Tail Recursion #

Recursive call is last operation:

function factorialTail(n, acc = 1) {
  if (n === 0) return acc;
  return factorialTail(n - 1, n * acc);
}

Tips for Writing Recursive Functions #

Identify base case(s) - When to stop?
Define recursive case - How to break down problem?
Make progress - Each call should move toward base case
Test base cases - Verify they return correct values
Trust the recursion - Don’t try to trace all calls
Consider memoization - For overlapping subproblems
Watch stack depth - Be careful with deep recursion

Common Mistakes #

Missing base case - Infinite recursion
Wrong base case - Incorrect results
Not making progress - Never reaches base case
Modifying arguments - Unintended side effects
Stack overflow - Too many recursive calls

Debugging Recursion #

function factorialDebug(n, depth = 0) {
  const indent = ' '.repeat(depth * 2);
  console.log(`${indent}factorial(${n}) called`);

  if (n === 0) {
    console.log(`${indent}Base case: returning 1`);
    return 1;
  }

  const result = n * factorialDebug(n - 1, depth + 1);
  console.log(`${indent}factorial(${n}) = ${result}`);
  return result;
}

factorialDebug(3);

Recursion is a powerful technique for solving complex problems elegantly. Master these patterns and you’ll be able to tackle tree, graph, and divide-and-conquer problems with confidence.