Skip to main content
Mapagam

Using Recursion Patterns

1. Understanding Recursion Fundamentals

Concept Description Key Properties
Base Case The condition that stops the recursion Ensures termination, prevents infinite loops
Recursive Case The function calling itself with modified parameters Progresses toward base case, maintains problem structure
Call Stack Memory structure storing function calls during execution Tracks local variables, return addresses

Example: Factorial Calculation

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

console.log(factorial(5)); // Output: 120
Note: Each recursive call adds a new frame to the call stack until the base case is reached.

Recursion Execution Flow

  1. Function is called with input parameter
  2. Check if base case is met
  3. If not, make recursive call with updated parameter
  4. Continue until base case is reached
  5. Return values propagate back up the call stack

Core Principles of Recursion

  • Must have a well-defined base case to prevent infinite recursion
  • Each recursive call must move closer to the base case
  • The problem should be divisible into smaller subproblems of the same type
  • Recursive solutions often mirror mathematical definitions

2. Implementing Tail Recursion Optimization

Aspect Description Notes
Definition Tail recursion occurs when the recursive call is the last operation in the function. Optimization can convert tail recursion into iteration.
Example (JavaScript) 
function sumTailRec(n, acc = 0) {
  if (n === 0) return acc;
  return sumTailRec(n - 1, acc + n);
}
 Accumulator pattern used to pass state forward.
Optimization Potential Some compilers/interpreters optimize tail recursion into loops. Not guaranteed in all environments (e.g., JavaScript engines).

Example: Tail Recursion vs Regular Recursion

// Regular recursion (not tail-optimized)
function factorial(n) {
  if (n === 0) return 1;
  return n * factorial(n - 1);
}

// Tail-recursive version
function factorialTail(n, acc = 1) {
  if (n === 0) return acc;
  return factorialTail(n - 1, n * acc);
}
Note: While tail recursion is a powerful pattern, JavaScript engines do not always optimize it. For performance-critical code, consider iterative alternatives.

3. Converting Recursion to Iteration

Recursion Pattern Iteration Equivalent Notes
Tail Recursion while (condition) { ... } Can be directly converted to a loop without stack buildup
Tree Traversal (Post-order) Stack-based traversal with explicit state tracking Use a stack to simulate the call stack behavior
Divide and Conquer Iterative divide with loop control Simulate recursive splits using a queue or stack

Example: Converting Tail Recursion to Loop

// Recursive version
function sumRecursive(n, acc = 0) {
  if (n === 0) return acc;
  return sumRecursive(n - 1, acc + n);
}

// Iterative version
function sumIterative(n) {
  let acc = 0;
  while (n > 0) {
    acc += n;
    n--;
  }
  return acc;
}

Example: Tree Traversal (Post-order)

// Recursive version
function postOrder(node) {
  if (!node) return;
  postOrder(node.left);
  postOrder(node.right);
  console.log(node.value);
}

// Iterative version using stack
function postOrderIterative(root) {
  const stack = [root];
  const result = [];

  while (stack.length > 0) {
    const node = stack.pop();
    if (node) {
      result.push(node.value);
      stack.push(node.left);
      stack.push(node.right);
    }
  }

  // Reverse to get post-order
  return result.reverse();
}
Note: For complex recursive patterns like binary tree traversals, the iterative version requires careful handling of state and may involve additional data structures like stacks or queues.

4. Calculating Factorials Recursively

Method Description Code Example Notes
Base Case Factorial of 0 or 1 is 1 n === 0 || n === 1 Stops the recursion
Recursive Case Factorial of n is n * factorial(n - 1) n * factorial(n - 1) Breaks problem into smaller subproblems

Example: Calculating Factorial

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

console.log(factorial(5)); // Output: 120
Note: For large values of n, recursion can lead to stack overflow errors. Consider iterative approaches for better performance in such cases.

5. Generating Fibonacci Numbers

Approach Description Time Complexity Space Complexity
Recursive Basic recursive implementation without memoization O(2^n) O(n)
Memoized Recursive Recursive with caching of previously computed values O(n) O(n)
Iterative Bottom-up approach using loop and variables O(n) O(1)
Matrix Exponentiation Using matrix multiplication to compute Fibonacci numbers O(log n) O(log n)

Example: Memoized Recursive Implementation

const fibMemo = (n, memo = {}) => {
  if (n in memo) return memo[n];
  if (n <= 1) return n;
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
};

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

Example: Iterative Implementation

function fibIterative(n) {
  if (n <= 1) return n;
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}

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

Example: Matrix Exponentiation Implementation

function matrixMultiply(A, B) {
  return [
    [A[0][0]*B[0][0] + A[0][1]*B[1][0], A[0][0]*B[0][1] + A[0][1]*B[1][1]],
    [A[1][0]*B[0][0] + A[1][1]*B[1][0], A[1][0]*B[0][1] + A[1][1]*B[1][1]]
  ];
}

function matrixPower(matrix, n) {
  if (n === 1) return matrix;
  if (n % 2 === 0) {
    const half = matrixPower(matrix, n / 2);
    return matrixMultiply(half, half);
  } else {
    return matrixMultiply(matrix, matrixPower(matrix, n - 1));
  }
}

function fibMatrix(n) {
  if (n <= 1) return n;
  const baseMatrix = [[1, 1], [1, 0]];
  const resultMatrix = matrixPower(baseMatrix, n);
  return resultMatrix[0][1];
}

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

6. Computing Power Function

Method Description Time Complexity Space Complexity
Iterative Uses a loop to multiply the base by itself n times. O(n) O(1)
Recursive Recursively computes power by dividing exponent in half. O(log n) O(log n)
Fast Exponentiation (Binary) Uses binary representation of exponent to reduce operations. O(log n) O(log n)

Example: Recursive Power Function

function power(base, exp) {
  if (exp === 0) return 1;
  if (exp === 1) return base;
  
  const half = power(base, Math.floor(exp / 2));
  
  if (exp % 2 === 0) {
    return half * half;
  } else {
    return base * half * half;
  }
}

// Example usage:
console.log(power(2, 10)); // Output: 1024

Example: Iterative Power Function

function powerIterative(base, exp) {
  let result = 1;
  while (exp > 0) {
    if (exp % 2 === 1) {
      result *= base;
    }
    base *= base;
    exp = Math.floor(exp / 2);
  }
  return result;
}

// Example usage:
console.log(powerIterative(3, 4)); // Output: 81

7. Calculating GCD

The Greatest Common Divisor (GCD) of two numbers is the largest positive integer that divides both numbers without remainder. The Euclidean algorithm is a classic recursive approach to compute GCD.

Method Description Implementation Notes
Recursive Euclidean Algorithm Repeatedly applies the property that GCD(a, b) = GCD(b, a mod b) 
function gcd(a, b) {
  if (b === 0) return a;
  return gcd(b, a % b);
}
 Base case: when b is 0, return a
Iterative Euclidean Algorithm Same logic but implemented with a loop instead of recursion 
function gcd(a, b) {
  while (b !== 0) {
    let temp = b;
    b = a % b;
    a = temp;
  }
  return a;
}
 More memory efficient for large inputs

Example: Calculating GCD of 48 and 18

gcd(48, 18) // Returns 6
// Step-by-step:
// gcd(48, 18) → gcd(18, 48 % 18) → gcd(18, 12)
// gcd(18, 12) → gcd(12, 18 % 12) → gcd(12, 6)
// gcd(12, 6) → gcd(6, 12 % 6) → gcd(6, 0)
// Returns 6
Note: The recursive approach is more intuitive and mirrors the mathematical definition closely.
Warning: For very large numbers, recursion depth might exceed limits in some environments.

8. Reversing Strings Recursively

Method Description Example
Base Case When string length is 0 or 1, return the string itself if (str.length <= 1) return str;
Recursive Case Take first character and append it to the end of reversed rest return reverse(str.slice(1)) + str[0];

Example: Reverse String Using Recursion

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

console.log(reverseString("hello")); // "olleh"
Note: This approach has O(n²) time complexity due to string concatenation in JavaScript.

9. Implementing Tree Traversals

Traversal Type Order of Visits Code Example Use Case
Inorder Left → Root → Right 
function inorder(node) {
  if (node) {
    inorder(node.left);
    console.log(node.value);
    inorder(node.right);
  }
}
 Sorted output for BST
Preorder Root → Left → Right 
function preorder(node) {
  if (node) {
    console.log(node.value);
    preorder(node.left);
    preorder(node.right);
  }
}
 Copy tree structure
Postorder Left → Right → Root 
function postorder(node) {
  if (node) {
    postorder(node.left);
    postorder(node.right);
    console.log(node.value);
  }
}
 Calculate sizes, delete nodes

Example: Inorder Traversal of BST

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

let root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(15);
root.left.right = new TreeNode(7);

function inorder(node) {
  if (node) {
    inorder(node.left);
    console.log(node.value); // 5, 7, 10, 15
    inorder(node.right);
  }
}

inorder(root);

10. Generating All Subsets

Approach Description Time Complexity Space Complexity
Recursive Generate subsets by including or excluding each element recursively. O(2^n) O(n)
Iterative Start with an empty subset and iteratively add elements to existing subsets. O(2^n) O(1) (excluding output)
Bit Manipulation Use bitmasks to represent subset inclusion; iterate from 0 to 2^n - 1. O(n * 2^n) O(1) (excluding output)

Example: Recursive Approach

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

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

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

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

// Example usage:
const nums = [1, 2, 3];
console.log(generateSubsets(nums));
// Output: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

Example: Iterative Approach

function generateSubsets(nums) {
  let result = [[]];

  for (const num of nums) {
    const newSubsets = [];
    for (const subset of result) {
      newSubsets.push([...subset, num]);
    }
    result = [...result, ...newSubsets];
  }

  return result;
}

// Example usage:
const nums = [1, 2, 3];
console.log(generateSubsets(nums));
// Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Example: Bit Manipulation Approach

function generateSubsets(nums) {
  const result = [];
  const n = nums.length;
  const totalSubsets = 1 << n;

  for (let i = 0; i < totalSubsets; i++) {
    const subset = [];
    for (let j = 0; j < n; j++) {
      if (i & (1 << j)) {
        subset.push(nums[j]);
      }
    }
    result.push(subset);
  }

  return result;
}

// Example usage:
const nums = [1, 2, 3];
console.log(generateSubsets(nums));
// Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

11. Implementing Merge Sort

Merge Sort is a divide-and-conquer algorithm that divides the input array into two halves, recursively sorts them, and then merges the sorted halves.

Property Description Example
Time Complexity Best, Average, and Worst case: O(n log n) O(n log n)
Space Complexity O(n) due to auxiliary space for merging O(n)
Stability Stable sorting algorithm Yes
Paradigm Divide and Conquer Divide, conquer, combine

Example: Merge Sort Implementation in JavaScript

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) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;

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

  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

// Example usage:
const array = [38, 27, 43, 3, 9, 82, 10];
console.log(mergeSort(array)); // [3, 9, 10, 27, 38, 43, 82]
Note: Merge Sort is stable and guarantees O(n log n) performance in all cases, making it ideal for applications where consistent performance is required.

12. Solving Tower of Hanoi Problem

The Tower of Hanoi is a classic recursive problem that involves moving disks between rods according to specific rules.

Parameter Description Values
n Number of disks int
source Starting rod string
destination Target rod string
auxiliary Helper rod string

Example: Recursive Solution

function hanoi(n, source, destination, auxiliary) {
  if (n === 1) {
    console.log(`Move disk from ${source} to ${destination}`);
    return;
  }

  hanoi(n - 1, source, auxiliary, destination);
  console.log(`Move disk from ${source} to ${destination}`);
  hanoi(n - 1, auxiliary, destination, source);
}

hanoi(3, 'A', 'C', 'B');
Note: The recursive approach breaks the problem into smaller subproblems. For n disks, it takes 2^n - 1 moves.

Was this article helpful?

Related Cheat Sheets