Recursion

November 19, 2025
#recursion #recursive-functions #algorithms #backtracking #divide-and-conquer #interviewing

Table of Contents

Introduction

Recursion is a programming technique where a function calls itself to solve a problem by breaking it down into smaller, similar subproblems. Think of Russian nesting dolls—each doll contains a smaller version of itself until you reach the smallest one that doesn’t open.

Recursion is fundamental to computer science and appears in tree traversals, sorting algorithms, mathematical computations, and backtracking problems. While it can seem magical at first, understanding recursion unlocks powerful problem-solving techniques.

Review Functions and Big-O Notation first if needed. Recursion is heavily used in DFS and tree algorithms.

What is recursion?

A recursive function has two essential components:

1. Base Case

The stopping condition that prevents infinite recursion.

if (n === 0) return 1; // Base case

2. Recursive Case

The function calling itself with a simpler input.

return n * factorial(n - 1); // Recursive case

Anatomy of recursion:

factorial(4)
  → 4 * factorial(3)
       → 3 * factorial(2)
            → 2 * factorial(1)
                 → 1 * factorial(0)
                      → 1 (base case)
                 ← 1
            ← 2
       ← 6
  ← 24

Why use recursion?

Choose recursion when:

  1. Problem has self-similar substructure (trees, graphs)
  2. Problem naturally defined recursively (factorial, Fibonacci)
  3. You need backtracking (maze solving, permutations)
  4. You’re implementing divide and conquer (merge sort, quick sort)
  5. Recursive solution is cleaner than iterative

Avoid recursion when:

  • Recursion depth is very large (stack overflow risk)
  • Iterative solution is simpler and more efficient
  • You need optimal space complexity (recursion uses O(n) stack space)
  • Performance is critical and recursion overhead matters

Basic recursive examples

1. Factorial

function factorial(n) {
  // Base case
  if (n === 0 || n === 1) return 1;

  // Recursive case
  return n * factorial(n - 1);
}

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

// Iterative version for comparison
function factorialIterative(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

def factorial(n):
    # Base case
    if n == 0 or n == 1:
        return 1

    # Recursive case
    return n * factorial(n - 1)

print(factorial(5))  # 120
print(factorial(0))  # 1

# Iterative version for comparison
def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

public class Recursion {
    public static int factorial(int n) {
        // Base case
        if (n == 0 || n == 1) {
            return 1;
        }

        // Recursive case
        return n * factorial(n - 1);
    }

    // Iterative version for comparison
    public static int factorialIterative(int n) {
        int result = 1;
        for (int i = 2; i <= n; i++) {
            result *= i;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(factorial(5));  // 120
        System.out.println(factorial(0));  // 1
    }
}

2. Fibonacci sequence

// Naive recursive (inefficient - O(2^n))
function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(6));  // 8
// But fibonacci(40) would be very slow!

// Optimized with memoization
function fibonacciMemo(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;

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

console.log(fibonacciMemo(40));  // 102334155 (fast!)

# Naive recursive (inefficient - O(2^n))
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(6))  # 8

# Optimized with memoization
def fibonacci_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n

    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

print(fibonacci_memo(40))  # 102334155 (fast!)

import java.util.HashMap;
import java.util.Map;

public class Fibonacci {
    // Naive recursive (inefficient)
    public static int fibonacci(int n) {
        if (n <= 1) return n;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    // Optimized with memoization
    public static int fibonacciMemo(int n, Map<Integer, Integer> memo) {
        if (memo.containsKey(n)) return memo.get(n);
        if (n <= 1) return n;

        int result = fibonacciMemo(n - 1, memo) +
                    fibonacciMemo(n - 2, memo);
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(6));  // 8
        System.out.println(fibonacciMemo(40, new HashMap<>()));
        // 102334155
    }
}

3. Sum of array

function sumArray(arr, index = 0) {
  // Base case: reached end of array
  if (index >= arr.length) return 0;

  // Recursive case: current element + sum of rest
  return arr[index] + sumArray(arr, index + 1);
}

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

def sum_array(arr, index=0):
    # Base case: reached end of array
    if index >= len(arr):
        return 0

    # Recursive case: current element + sum of rest
    return arr[index] + sum_array(arr, index + 1)

print(sum_array([1, 2, 3, 4, 5]))  # 15

public static int sumArray(int[] arr, int index) {
    // Base case: reached end of array
    if (index >= arr.length) {
        return 0;
    }

    // Recursive case: current element + sum of rest
    return arr[index] + sumArray(arr, index + 1);
}

System.out.println(sumArray(new int[]{1, 2, 3, 4, 5}, 0));  // 15

Tree recursion examples

Binary tree height

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

function treeHeight(node) {
  // Base case: empty tree
  if (node === null) return 0;

  // Recursive case: 1 + max of subtree heights
  const leftHeight = treeHeight(node.left);
  const rightHeight = treeHeight(node.right);
  return 1 + Math.max(leftHeight, rightHeight);
}

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);

console.log(treeHeight(root));  // 3

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def tree_height(node):
    # Base case: empty tree
    if node is None:
        return 0

    # Recursive case: 1 + max of subtree heights
    left_height = tree_height(node.left)
    right_height = tree_height(node.right)
    return 1 + max(left_height, right_height)

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)

print(tree_height(root))  # 3

class TreeNode {
    int value;
    TreeNode left, right;
    TreeNode(int value) { this.value = value; }
}

public static int treeHeight(TreeNode node) {
    // Base case: empty tree
    if (node == null) return 0;

    // Recursive case: 1 + max of subtree heights
    int leftHeight = treeHeight(node.left);
    int rightHeight = treeHeight(node.right);
    return 1 + Math.max(leftHeight, rightHeight);
}

TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);

System.out.println(treeHeight(root));  // 3

Backtracking with recursion

Generate all permutations

function permutations(arr) {
  const result = [];

  function backtrack(current, remaining) {
    // Base case: no more elements to add
    if (remaining.length === 0) {
      result.push([...current]);
      return;
    }

    // Try each remaining element
    for (let i = 0; i < remaining.length; i++) {
      current.push(remaining[i]);

      // Recurse with updated arrays
      const newRemaining = [...remaining.slice(0, i),
                           ...remaining.slice(i + 1)];
      backtrack(current, newRemaining);

      current.pop(); // Backtrack
    }
  }

  backtrack([], arr);
  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]]

def permutations(arr):
    result = []

    def backtrack(current, remaining):
        # Base case: no more elements to add
        if not remaining:
            result.append(current[:])
            return

        # Try each remaining element
        for i in range(len(remaining)):
            current.append(remaining[i])

            # Recurse with updated arrays
            new_remaining = remaining[:i] + remaining[i+1:]
            backtrack(current, new_remaining)

            current.pop()  # Backtrack

    backtrack([], arr)
    return result

print(permutations([1, 2, 3]))
# [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

import java.util.*;

public class Permutations {
    public static List<List<Integer>> permutations(int[] arr) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> arrList = new ArrayList<>();
        for (int num : arr) arrList.add(num);

        backtrack(new ArrayList<>(), arrList, result);
        return result;
    }

    private static void backtrack(List<Integer> current,
                                  List<Integer> remaining,
                                  List<List<Integer>> result) {
        // Base case
        if (remaining.isEmpty()) {
            result.add(new ArrayList<>(current));
            return;
        }

        // Try each remaining element
        for (int i = 0; i < remaining.size(); i++) {
            current.add(remaining.get(i));

            List<Integer> newRemaining = new ArrayList<>(remaining);
            newRemaining.remove(i);
            backtrack(current, newRemaining, result);

            current.remove(current.size() - 1); // Backtrack
        }
    }

    public static void main(String[] args) {
        System.out.println(permutations(new int[]{1, 2, 3}));
    }
}

N-Queens problem

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

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

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

    // Check diagonal (top-right)
    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) {
    // Base case: placed all queens
    if (row === n) {
      result.push(board.map(r => r.join('')));
      return;
    }

    // Try placing queen in each column
    for (let col = 0; col < n; col++) {
      if (isSafe(row, col)) {
        board[row][col] = 'Q'; // Place queen
        backtrack(row + 1);    // Recurse
        board[row][col] = '.'; // Backtrack
      }
    }
  }

  backtrack(0);
  return result;
}

console.log(solveNQueens(4));
// [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Divide and conquer with recursion

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 case: search left or right half
  if (arr[mid] > target) {
    return binarySearch(arr, target, left, mid - 1);
  } else {
    return binarySearch(arr, target, mid + 1, right);
  }
}

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

Merge sort

function mergeSort(arr) {
  // Base case: array of 0 or 1 element
  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([5, 2, 8, 1, 9, 3]));  // [1, 2, 3, 5, 8, 9]

Common recursion patterns

1. Linear recursion

Single recursive call (factorial, sum)

2. Binary recursion

Two recursive calls (Fibonacci, binary tree)

3. Tail recursion

Recursive call is last operation (optimizable)

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

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

4. Mutual recursion

Functions calling each other

function isEven(n) {
  if (n === 0) return true;
  return isOdd(n - 1);
}

function isOdd(n) {
  if (n === 0) return false;
  return isEven(n - 1);
}

Complexity analysis

  • Time: Depends on problem (often O(2^n) for naive, O(n) optimized)
  • Space: O(n) for call stack depth in most cases

Common pitfalls

  • Missing base case: Infinite recursion → stack overflow
  • Wrong base case: Incorrect results or non-termination
  • Not making progress: Each recursive call must move toward base case
  • Inefficient recursion: Multiple redundant calculations (use memoization)
  • Stack overflow: Very deep recursion exhausts call stack
  • Modifying shared state: Be careful with global variables

When to use recursion

  • Tree/graph traversal: Natural recursive structure
  • Divide and conquer: Binary search, merge sort, quick sort
  • Backtracking: N-Queens, Sudoku, permutations
  • Mathematical: Factorial, Fibonacci, combinations
  • Nested structures: Parsing, expression evaluation

Practice problems

  1. Power function (x^n) with O(log n) complexity
  2. Reverse a string recursively
  3. Check if string is palindrome (recursive)
  4. Tower of Hanoi
  5. Generate all subsets of a set
  6. Count ways to climb stairs (1 or 2 steps at a time)
  7. Decode ways (letter combinations)
  8. Word break problem
  9. Generate valid parentheses combinations
  10. Combination sum
  11. Sudoku solver
  12. Regular expression matching
  13. Letter combinations of phone number
  14. Flatten nested list
  15. Evaluate expression tree

Complexity summary

  • Time: Varies greatly (O(n), O(n log n), O(2^n), etc.)
  • Space: O(d) where d is max recursion depth (call stack)

Recursion is a powerful tool that simplifies complex problems with self-similar structure. Master recursion and you’ll be able to elegantly solve problems involving trees, graphs, backtracking, and divide-and-conquer algorithms.

Thanks for visiting
We are actively updating content to this site. Thanks for visiting! Please bookmark this page and visit again soon.
Sponsor