Recursive Functions: Solving Problems by Calling Functions Themselves

What is Recursion

Stand between two parallel mirrors and you'll see countless reflections of yourself—each reflection contains a smaller reflection, extending infinitely into the distance. This is the intuitive embodiment of recursion: self-reference, self-inclusion.

In programming, recursion is a technique where a function calls itself. A recursive function breaks down a large problem into smaller identical problems until the problem becomes small enough to solve directly.

Recursion has two key elements:

1. Base Case: The termination condition of recursion
2. Recursive Case: The function calls itself to solve smaller problems

Understanding Recursive Thinking

1. The Simplest Recursion Example

// Countdown: Count from n to 1
function countdown(n) {
  // Base case: Stop when n is 0
  if (n === 0) {
    console.log("Launch!");
    return;
  }

  // Recursive case: Output current number, then recursively call with smaller number
  console.log(n);
  countdown(n - 1);
}

countdown(5);
// 5
// 4
// 3
// 2
// 1
// Launch!

How does this function work? Let's trace the call stack:

countdown(5)
  -> Output 5, call countdown(4)
    -> Output 4, call countdown(3)
      -> Output 3, call countdown(2)
        -> Output 2, call countdown(1)
          -> Output 1, call countdown(0)
            -> Output "Launch!", return
          <- Return
        <- Return
      <- Return
    <- Return
  <- Return

2. Calculating Factorial

Factorial is a classic example of recursion. 5! = 5 × 4 × 3 × 2 × 1 = 120:

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

  // Recursive case: n! = n × (n-1)!
  return n * factorial(n - 1);
}

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

// Compare with iterative approach
function factorialIterative(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

The recursive version is closer to the mathematical definition and easier to understand, but it creates multiple function calls.

3. Fibonacci Sequence

Each number is the sum of the two preceding numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21...

// Basic recursive implementation
function fibonacci(n) {
  // Base case
  if (n <= 1) {
    return n;
  }

  // Recursive case: fib(n) = fib(n-1) + fib(n-2)
  return fibonacci(n - 1) + fibonacci(n - 2);
}

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

// Call tree visualization (fibonacci(5))
//                 fib(5)
//              /          \
//         fib(4)          fib(3)
//        /      \        /      \
//    fib(3)   fib(2)  fib(2)  fib(1)
//    /   \    /   \   /   \
// fib(2) fib(1) ...  ...
// Note: Lots of repeated calculations!

Common Recursion Patterns

1. Summing Arrays

// Recursive sum
function sum(arr) {
  // Base case: Empty array
  if (arr.length === 0) {
    return 0;
  }

  // Recursive case: First element + sum of remaining elements
  return arr[0] + sum(arr.slice(1));
}

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

// More efficient tail recursive version
function sumTail(arr, accumulator = 0) {
  if (arr.length === 0) {
    return accumulator;
  }

  return sumTail(arr.slice(1), accumulator + arr[0]);
}

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

2. Finding Maximum Value

function findMax(arr) {
  // Base case: Only one element
  if (arr.length === 1) {
    return arr[0];
  }

  // Recursive case: Current element vs maximum of remaining elements
  const maxOfRest = findMax(arr.slice(1));
  return arr[0] > maxOfRest ? arr[0] : maxOfRest;
}

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

3. Array Flattening

// Recursively flatten nested arrays
function flatten(arr) {
  let result = [];

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

  return result;
}

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

// Functional version
function flattenFunctional(arr) {
  return arr.reduce(
    (acc, item) =>
      Array.isArray(item)
        ? acc.concat(flattenFunctional(item))
        : acc.concat(item),
    []
  );
}

Recursive Tree Traversal

Recursion is particularly suitable for handling tree structures:

1. DOM Tree Traversal

// Recursively traverse DOM tree
function traverseDOM(node, callback, level = 0) {
  // Base case: No node
  if (!node) return;

  // Process current node
  callback(node, level);

  // Recursively process child nodes
  for (const child of node.children) {
    traverseDOM(child, callback, level + 1);
  }
}

// Usage example
traverseDOM(document.body, (node, level) => {
  const indent = "  ".repeat(level);
  console.log(
    `${indent}${node.tagName} #${node.id || ""} .${node.className || ""}`
  );
});

2. File System Traversal

// Recursively traverse file system structure
function traverseFileSystem(node, callback, path = "") {
  const currentPath = path + "/" + node.name;

  // Process current node
  callback(node, currentPath);

  // If it's a directory, recursively process children
  if (node.type === "directory" && node.children) {
    for (const child of node.children) {
      traverseFileSystem(child, callback, currentPath);
    }
  }
}

// Sample data
const fileSystem = {
  name: "root",
  type: "directory",
  children: [
    {
      name: "documents",
      type: "directory",
      children: [
        { name: "resume.pdf", type: "file" },
        { name: "letter.docx", type: "file" },
      ],
    },
    {
      name: "images",
      type: "directory",
      children: [{ name: "photo1.jpg", type: "file" }],
    },
    { name: "notes.txt", type: "file" },
  ],
};

// Usage
traverseFileSystem(fileSystem, (node, path) => {
  const type = node.type === "directory" ? "📁" : "📄";
  console.log(`${type} ${path}`);
});

3. JSON Deep Clone

function deepClone(obj) {
  // Base case: Primitive types
  if (obj === null || typeof obj !== "object") {
    return obj;
  }

  // Handle arrays
  if (Array.isArray(obj)) {
    return obj.map((item) => deepClone(item));
  }

  // Handle dates
  if (obj instanceof Date) {
    return new Date(obj);
  }

  // Handle objects
  const cloned = {};
  for (const key in obj) {
    if (obj.hasOwnProperty(key)) {
      cloned[key] = deepClone(obj[key]);
    }
  }

  return cloned;
}

// Test
const original = {
  name: "John",
  age: 30,
  address: {
    city: "New York",
    coordinates: {
      lat: 40.7128,
      lng: -74.006,
    },
  },
  hobbies: ["reading", "coding"],
  joined: new Date("2020-01-01"),
};

const cloned = deepClone(original);
cloned.address.city = "Los Angeles";

console.log(original.address.city); // "New York" (unchanged)
console.log(cloned.address.city); // "Los Angeles"

Recursion Optimization

1. Tail Recursion Optimization

Tail recursion means the recursive call is the last operation of the function:

// ❌ Non-tail recursive - There's still operation after recursive call (multiplication)
function factorial(n) {
  if (n === 0) return 1;
  return n * factorial(n - 1); // Still need to do multiplication
}

// ✅ Tail recursive - Recursive call is the last operation
function factorialTail(n, accumulator = 1) {
  if (n === 0) return accumulator;
  return factorialTail(n - 1, n * accumulator); // Last operation
}

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

The advantage of tail recursion is that it can be optimized by the compiler into iteration, avoiding stack growth.

2. Trampoline Function

JavaScript doesn't guarantee tail recursion optimization, but we can simulate it with trampoline functions:

// Trampoline function
function trampoline(fn) {
  return function (...args) {
    let result = fn(...args);

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

    return result;
  };
}

// Transform into trampoline version of Fibonacci
function fibTrampoline(n, a = 0, b = 1) {
  if (n === 0) return a;
  if (n === 1) return b;

  // Return a function instead of direct recursion
  return () => fibTrampoline(n - 1, b, a + b);
}

const fib = trampoline(fibTrampoline);
console.log(fib(10)); // 55
console.log(fib(1000)); // Can handle large numbers without stack overflow

3. Memoized Recursion

Avoid repeated calculations through caching:

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(...args);
    cache.set(key, result);
    return result;
  };
}

// Memoized Fibonacci
const fibonacci = memoize(function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
});

console.time("fib(40)");
console.log(fibonacci(40)); // 102334155
console.timeEnd("fib(40)"); // A few milliseconds

// Compare with unoptimized version
function fibSlow(n) {
  if (n <= 1) return n;
  return fibSlow(n - 1) + fibSlow(n - 2);
}

console.time("fibSlow(40)");
console.log(fibSlow(40)); // 102334155
console.timeEnd("fibSlow(40)"); // Several seconds!

Real-world Applications of Recursion

1. Permutations and Combinations

// Generate all permutations of an array
function permutations(arr) {
  // Base case: Empty or single-element array
  if (arr.length <= 1) {
    return [arr];
  }

  const result = [];

  // For each element as the first element
  for (let i = 0; i < arr.length; i++) {
    const current = arr[i];
    const remaining = [...arr.slice(0, i), ...arr.slice(i + 1)];

    // Recursively get permutations of remaining elements
    const remainingPerms = permutations(remaining);

    // Add current element to the beginning of each permutation
    for (const perm of remainingPerms) {
      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 combinations
function combinations(arr, k) {
  // Base case
  if (k === 0) return [[]];
  if (arr.length === 0) return [];

  const [first, ...rest] = arr;

  // Combinations including first element
  const withFirst = combinations(rest, k - 1).map((combo) => [first, ...combo]);

  // Combinations not including first element
  const withoutFirst = combinations(rest, k);

  return [...withFirst, ...withoutFirst];
}

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

2. Quick Sort

function quickSort(arr) {
  // Base case: Empty or single-element array is already sorted
  if (arr.length <= 1) {
    return arr;
  }

  // Select pivot value (choose middle element here)
  const pivotIndex = Math.floor(arr.length / 2);
  const pivot = arr[pivotIndex];

  // Partition
  const left = [];
  const equal = [];
  const right = [];

  for (const item of arr) {
    if (item < pivot) {
      left.push(item);
    } else if (item === pivot) {
      equal.push(item);
    } else {
      right.push(item);
    }
  }

  // Recursively sort left and right partitions, then merge
  return [...quickSort(left), ...equal, ...quickSort(right)];
}

const numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
console.log(quickSort(numbers));
// [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

3. Path Finding

// Find path in maze
function findPath(maze, start, end, path = [], visited = new Set()) {
  const [x, y] = start;
  const [endX, endY] = end;
  const key = `${x},${y}`;

  // Out of bounds or visited
  if (x < 0 || y < 0 || x >= maze.length || y >= maze[0].length) {
    return null;
  }
  if (maze[x][y] === 1 || visited.has(key)) {
    return null;
  }

  // Found the end
  if (x === endX && y === endY) {
    return [...path, [x, y]];
  }

  // Mark as visited
  visited.add(key);
  const newPath = [...path, [x, y]];

  // Try four directions
  const directions = [
    [x + 1, y], // Down
    [x - 1, y], // Up
    [x, y + 1], // Right
    [x, y - 1], // Left
  ];

  for (const [nextX, nextY] of directions) {
    const result = findPath(
      maze,
      [nextX, nextY],
      end,
      newPath,
      new Set(visited)
    );

    if (result) {
      return result;
    }
  }

  return null;
}

// Maze: 0 = path, 1 = wall
const maze = [
  [0, 0, 1, 0],
  [0, 0, 0, 0],
  [1, 1, 0, 1],
  [0, 0, 0, 0],
];

const path = findPath(maze, [0, 0], [3, 3]);
console.log("Path:", path);

When to Use Recursion

Recursion is suitable for the following scenarios:

1. Tree structures: DOM traversal, file systems, JSON operations
2. Divide and conquer algorithms: Quick sort, merge sort, binary search
3. Backtracking problems: Mazes, eight queens, Sudoku
4. Mathematical problems: Factorial, Fibonacci, combinations
5. Self-similar problems: Fractals, recursive graphics

Recursion is not suitable for scenarios:

1. Simple loops: Use for/while which is simpler
2. Deep recursion: May cause stack overflow
3. Performance-critical code: Function call overhead is large

Summary

Recursion is a powerful programming technique that enables us to:

1. Solve complex problems with concise code: Especially tree and divide-and-conquer problems
2. Be closer to mathematical definitions: Recursive versions are usually easier to understand
3. Elegantly handle self-similar structures: Like trees, graphs, fractals

But also note:

• Ensure there's a clear base case to avoid infinite recursion
• Consider performance, use memoization or switch to iteration when necessary
• Pay attention to call stack depth limits

Mastering recursive thinking will give you a new perspective and tool for handling complex problems.

---