Code Templates

Use these recursive code templates as starting points for solving algorithmic problems. Each template includes the core recursive structure with explanations and optimization techniques.

Refer to the Concept Guide for theory and understanding.

Basic Recursion with Memoization

This is the foundational template for problems where you need to avoid redundant calculations. It works by storing results of expensive function calls and returning cached results when the same inputs occur again.

This template directly solves problems like Fibonacci and Climbing Stairs.

Implementation

/**
 * Basic recursion with memoization
 * Use when: Avoiding redundant calculations in recursive solutions
 * Time: O(n) with memoization vs O(2^n) without
 * Space: O(n) for memo cache + O(n) recursion stack
 */
function memoizedRecursion(n, memo = {}) {
    // Check memo cache first
    if (n in memo) return memo[n];

    // Base case: simplest problem that can be solved directly
    if (n <= 1) return 1;

    // Recursive case with memoization
    memo[n] = memoizedRecursion(n - 1, memo) + memoizedRecursion(n - 2, memo);
    return memo[n];
}

"""
Basic recursion with memoization
Use when: Avoiding redundant calculations in recursive solutions
Time: O(n) with memoization vs O(2^n) without
Space: O(n) for memo cache + O(n) recursion stack
"""
from functools import lru_cache

@lru_cache(maxsize=None)
def memoized_recursion(n):
    # Base case: simplest problem that can be solved directly
    if n <= 1:
        return 1

    # Recursive case automatically memoized by decorator
    return memoized_recursion(n - 1) + memoized_recursion(n - 2)

# Alternative: manual memoization
def manual_memo(n, memo=None):
    if memo is None:
        memo = {}

    # Check memo cache first
    if n in memo:
        return memo[n]

    # Base case
    if n <= 1:
        return 1

    # Recursive case with memoization
    memo[n] = manual_memo(n - 1, memo) + manual_memo(n - 2, memo)
    return memo[n]

/**
 * Basic recursion with memoization
 * Use when: Avoiding redundant calculations in recursive solutions
 * Time: O(n) with memoization vs O(2^n) without
 * Space: O(n) for memo cache + O(n) recursion stack
 */
public class MemoizationTemplate {
    private int[] memo;

    public int memoizedRecursion(int n) {
        memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return helper(n);
    }

    private int helper(int n) {
        // Check memo cache first
        if (memo[n] != -1) return memo[n];

        // Base case: simplest problem that can be solved directly
        if (n <= 1) return 1;

        // Recursive case with memoization
        memo[n] = helper(n - 1) + helper(n - 2);
        return memo[n];
    }
}

/**
 * Basic recursion with memoization
 * Use when: Avoiding redundant calculations in recursive solutions
 * Time: O(n) with memoization vs O(2^n) without
 * Space: O(n) for memo cache + O(n) recursion stack
 */
#include <vector>
#include <unordered_map>

class MemoizationTemplate {
private:
    std::unordered_map<int, int> memo;

public:
    int memoizedRecursion(int n) {
        // Check memo cache first
        if (memo.find(n) != memo.end()) {
            return memo[n];
        }

        // Base case: simplest problem that can be solved directly
        if (n <= 1) return 1;

        // Recursive case with memoization
        memo[n] = memoizedRecursion(n - 1) + memoizedRecursion(n - 2);
        return memo[n];
    }
};

/**
 * Basic recursion with memoization
 * Use when: Avoiding redundant calculations in recursive solutions
 * Time: O(n) with memoization vs O(2^n) without
 * Space: O(n) for memo cache + O(n) recursion stack
 */
func memoizedRecursion(n int) int {
    memo := make(map[int]int)
    return helper(n, memo)
}

func helper(n int, memo map[int]int) int {
    // Check memo cache first
    if val, exists := memo[n]; exists {
        return val
    }

    // Base case: simplest problem that can be solved directly
    if n <= 1 {
        return 1
    }

    // Recursive case with memoization
    result := helper(n-1, memo) + helper(n-2, memo)
    memo[n] = result
    return result
}

# Basic recursion with memoization
# Use when: Avoiding redundant calculations in recursive solutions
# Time: O(n) with memoization vs O(2^n) without
# Space: O(n) for memo cache + O(n) recursion stack
def memoized_recursion(n, memo = {})
  # Check memo cache first
  return memo[n] if memo.key?(n)

  # Base case: simplest problem that can be solved directly
  return 1 if n <= 1

  # Recursive case with memoization
  memo[n] = memoized_recursion(n - 1, memo) + memoized_recursion(n - 2, memo)
  memo[n]
end

Code Breakdown

Key Variables:

memo: Cache storing computed results (map, dict, hash table depending on language)
n: Input parameter defining problem size
Base case condition: n <= 1 (smallest solvable problem)

  graph TD
    subgraph RecursionFlow ["Recursive Execution Flow"]
        Start([Start]) --> CheckCache{Check<br/>Memo Cache}
        CheckCache -->|Found| ReturnCached[Return<br/>Cached Result]
        CheckCache -->|Not Found| CheckBase{Is<br/>Base Case?}
        CheckBase -->|Yes| ReturnBase[Return<br/>Base Result]
        CheckBase -->|No| Recurse1[Recursive Call<br/>n-1]
        Recurse1 --> Recurse2[Recursive Call<br/>n-2]
        Recurse2 --> Compute[Combine Results]
        Compute --> Store[Store in<br/>Memo Cache]
        Store --> ReturnResult[Return<br/>Final Result]

        style Start fill:#e1f5ff
        style ReturnCached fill:#ffe1e1
        style ReturnBase fill:#e1ffe1
        style ReturnResult fill:#fff4e1
    end

    CheckCache -.->|Hit| ReturnCached
    CheckCache -.->|Miss| CheckBase
    Store -.->|Save| ReturnResult

Critical Sections:

Initialization: Create memo cache (optional parameter for cleaner API)
Cache Check: First operation in every call
Base Case: Termination condition preventing infinite recursion
Recursive Calls: Make smaller subproblems
Result Storage: Cache before returning for future reuse

Backtracking Template

This template generates all valid combinations, permutations, or subsets by exploring possibilities, backtracking when hitting constraints. It’s essential for combinatorial problems.

This template directly solves problems like Subsets and Permutations.

Implementation

/**
 * Backtracking template for combinatorial problems
 * Use when: Generate all combinations/permutations with constraints
 * Time: O(2^n) or O(n!) depending on problem
 * Space: O(result) for storing solutions
 */
function backtrackingTemplate(nums, start = 0, current = [], result = []) {
    // Add current state to result (snapshot of valid combination)
    result.push([...current]);

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

        // Recurse to explore further choices
        backtrackingTemplate(nums, i + 1, current, result);

        // Backtrack: remove last added element to try next choice
        current.pop();
    }

    return result;
}

"""
Backtracking template for combinatorial problems
Use when: Generate all combinations/permutations with constraints
Time: O(2^n) or O(n!) depending on problem
Space: O(result) for storing solutions
"""
def backtracking_template(nums, start=0, current=None, result=None):
    if current is None:
        current = []
    if result is None:
        result = []

    # Add current state to result (snapshot of valid combination)
    result.append(current[:])

    # Try each remaining choice
    for i in range(start, len(nums)):
        # Include current element
        current.append(nums[i])

        # Recurse to explore further choices
        backtracking_template(nums, i + 1, current, result)

        # Backtrack: remove last added element
        current.pop()

    return result

/**
 * Backtracking template for combinatorial problems
 * Use when: Generate all combinations/permutations with constraints
 * Time: O(2^n) or O(n!) depending on problem
 * Space: O(result) for storing solutions
 */
public class BacktrackingTemplate {
    private List<List<Integer>> result;

    public List<List<Integer>> backtrackingTemplate(int[] nums) {
        result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>());
        return result;
    }

    private void backtrack(int[] nums, int start, List<Integer> current) {
        // Add current state to result (snapshot)
        result.add(new ArrayList<>(current));

        // Try each remaining choice
        for (int i = start; i < nums.length; i++) {
            // Include current element
            current.add(nums[i]);

            // Recurse to explore further choices
            backtrack(nums, i + 1, current);

            // Backtrack: remove last added element
            current.remove(current.size() - 1);
        }
    }
}

/**
 * Backtracking template for combinatorial problems
 * Use when: Generate all combinations/permutations with constraints
 * Time: O(2^n) or O(n!) depending on problem
 * Space: O(result) for storing solutions
 */
#include <vector>

class BacktrackingTemplate {
private:
    std::vector<std::vector<int>> result;

public:
    std::vector<std::vector<int>> backtrackingTemplate(std::vector<int>& nums) {
        std::vector<int> current;
        backtrack(nums, 0, current);
        return result;
    }

private:
    void backtrack(std::vector<int>& nums, int start, std::vector<int>& current) {
        // Add current state to result (snapshot)
        result.push_back(current);

        // Try each remaining choice
        for (int i = start; i < nums.size(); i++) {
            // Include current element
            current.push_back(nums[i]);

            // Recurse to explore further choices
            backtrack(nums, i + 1, current);

            // Backtrack: remove last added element
            current.pop_back();
        }
    }
};

/**
 * Backtracking template for combinatorial problems
 * Use when: Generate all combinations/permutations with constraints
 * Time: O(2^n) or O(n!) depending on problem
 * Space: O(result) for storing solutions
 */
func backtrackingTemplate(nums []int) [][]int {
    var result [][]int
    var current []int
    backtrack(nums, 0, current, &result)
    return result
}

func backtrack(nums []int, start int, current []int, result *[][]int) {
    // Add current state to result (snapshot - make copy)
    snapshot := make([]int, len(current))
    copy(snapshot, current)
    *result = append(*result, snapshot)

    // Try each remaining choice
    for i := start; i < len(nums); i++ {
        // Include current element
        current = append(current, nums[i])

        // Recurse to explore further choices
        backtrack(nums, i+1, current, result)

        // Backtrack: remove last added element
        current = current[:len(current)-1]
    }
}

# Backtracking template for combinatorial problems
# Use when: Generate all combinations/permutations with constraints
# Time: O(2^n) or O(n!) depending on problem
# Space: O(result) for storing solutions
def backtracking_template(nums, start = 0, current = [], result = [])
  # Add current state to result (snapshot)
  result << current.dup

  # Try each remaining choice
  (start...nums.length).each do |i|
    # Include current element
    current << nums[i]

    # Recurse to explore further choices
    backtracking_template(nums, i + 1, current, result)

    # Backtrack: remove last added element
    current.pop
  end

  result
end

Code Breakdown

Key Variables:

nums: Input array of choices
start: Index to begin trying choices (prevents reusing same element)
current: Current combination/path being built
result: Collection of all valid solutions

  graph TD
    subgraph BacktrackingFlow ["Backtracking Execution Flow"]
        Start([Start]) --> AddSnapshot[Add Current<br/>to Results]
        AddSnapshot --> LoopStart{For Each<br/>Choice}
        LoopStart -->|More Choices| Include[Include<br/>Choice]
        Include --> Recurse[Recursive Call<br/>Explore Deeper]
        Recurse --> Backtrack[Backtrack:<br/>Remove Choice]
        Backtrack --> LoopStart
        LoopStart -->|No More Choices| End([End])

        style Start fill:#e1f5ff
        style End fill:#e1ffe1
    end

Critical Sections:

Snapshot Capture: Copy current state before modification
Loop Through Choices: Iterate available options
Include Choice: Add to current state
Recurse: Explore combinations with this choice included
Backtrack: Remove choice to try next option (essential!)

Tree Recursion Template

This template handles binary tree problems by processing node, left subtree, and right subtree recursively. It’s the backbone of almost all tree algorithms.

This template directly solves problems like Maximum Depth of Binary Tree and Path Sum.

Implementation

/**
 * Tree recursion template for binary tree problems
 * Use when: Processing tree nodes recursively
 * Time: O(n) - visit each node once
 * Space: O(h) for recursion stack, h = tree height
 */
function treeRecursion(root) {
    // Base case: empty tree
    if (!root) return 0;

    // Process current node value
    const currentValue = root.val;

    // Recurse on left subtree
    const leftResult = treeRecursion(root.left);

    // Recurse on right subtree
    const rightResult = treeRecursion(root.right);

    // Combine results (example: max depth)
    return Math.max(leftResult, rightResult) + 1;
}

"""
Tree recursion template for binary tree problems
Use when: Processing tree nodes recursively
Time: O(n) - visit each node once
Space: O(h) for recursion stack, h = tree height
"""
def tree_recursion(root):
    # Base case: empty tree
    if not root:
        return 0

    # Process current node value
    current_val = root.val

    # Recurse on left subtree
    left_result = tree_recursion(root.left)

    # Recurse on right subtree
    right_result = tree_recursion(root.right)

    # Combine results (example: max depth)
    return max(left_result, right_result) + 1

/**
 * Tree recursion template for binary tree problems
 * Use when: Processing tree nodes recursively
 * Time: O(n) - visit each node once
 * Space: O(h) for recursion stack, h = tree height
 */
public int treeRecursion(TreeNode root) {
    // Base case: empty tree
    if (root == null) return 0;

    // Process current node value
    int currentValue = root.val;

    // Recurse on left subtree
    int leftResult = treeRecursion(root.left);

    // Recurse on right subtree
    int rightResult = treeRecursion(root.right);

    // Combine results (example: max depth)
    return Math.max(leftResult, rightResult) + 1;
}

/**
 * Tree recursion template for binary tree problems
 * Use when: Processing tree nodes recursively
 * Time: O(n) - visit each node once
 * Space: O(h) for recursion stack, h = tree height
 */
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int treeRecursion(TreeNode* root) {
    // Base case: empty tree
    if (!root) return 0;

    // Process current node value
    int currentValue = root->val;

    // Recurse on left subtree
    int leftResult = treeRecursion(root->left);

    // Recurse on right subtree
    int rightResult = treeRecursion(root->right);

    // Combine results (example: max depth)
    return std::max(leftResult, rightResult) + 1;
}

/**
 * Tree recursion template for binary tree problems
 * Use when: Processing tree nodes recursively
 * Time: O(n) - visit each node once
 * Space: O(h) for recursion stack, h = tree height
 */
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func treeRecursion(root *TreeNode) int {
    // Base case: empty tree
    if root == nil {
        return 0
    }

    // Process current node value
    currentVal := root.Val

    // Recurse on left subtree
    leftResult := treeRecursion(root.Left)

    // Recurse on right subtree
    rightResult := treeRecursion(root.Right)

    // Combine results (example: max depth)
    if leftResult > rightResult {
        return leftResult + 1
    }
    return rightResult + 1
}

# Tree recursion template for binary tree problems
# Use when: Processing tree nodes recursively
# Time: O(n) - visit each node once
# Space: O(h) for recursion stack, h = tree height
def tree_recursion(root)
  # Base case: empty tree
  return 0 unless root

  # Process current node value
  current_val = root.val

  # Recurse on left subtree
  left_result = tree_recursion(root.left)

  # Recurse on right subtree
  right_result = tree_recursion(root.right)

  # Combine results (example: max depth)
  [left_result, right_result].max + 1
end

Code Breakdown

Key Variables:

root: Current tree node being processed
currentValue: Data at current node
leftResult: Result from left subtree
rightResult: Result from right subtree

  graph TD
    subgraph TreeRecursion ["Tree Recursion Execution"]
        Current[Current Node] --> CheckNull{Is<br/>Null?}
        CheckNull -->|Yes| ReturnBase[Return<br/>Base Case]
        CheckNull -->|No| Process[Process<br/>Current]
        Process --> RecurseLeft[Recurse on<br/>Left Child]
        RecurseLeft --> RecurseRight[Recurse on<br/>Right Child]
        RecurseRight --> Combine[Combine Results<br/>and Return]

        style ReturnBase fill:#e1ffe1
        style Current fill:#e1f5ff
        style Combine fill:#fff4e1
    end

Critical Sections:

Base Case: Check for null (empty tree) first
Process Node: Read/use current node’s value
Recurse Left: Call on left child (may be null)
Recurse Right: Call on right child (may be null)
Combine: Merge results from both subtrees with current node

Pro Tip: When recursion stack is an issue, convert to iterative approach. For memoized recursion, consider switching to bottom-up dynamic programming for better space efficiency.

Practice

Ready to apply these templates? Check out our Practice Problems for hands-on coding challenges.