Recursion: Code Templates in 6 Languages

Coding Patterns - Guide to 30 Core Algorithm Patterns

Recursion: Complete Guide to Base Cases and Memoization

If you have not read the concept guide yet, start there for the theory and complexity analysis. This page gives you four recursive skeletons you can reuse for most recursion problems in an interview. Each one has the same two-part spine: a base case that stops the recursion, and a recursive case that reduces the problem and combines results.

Main Template: Memoized Recursion

The most common form of recursion caches its results. Instead of recomputing f(n-1) and f(n-2) on every branch, each distinct argument is computed exactly once and stored. This turns an exponential call tree into a linear one without changing the shape of the code.

Use this for Fibonacci Number and Climbing Stairs .

    graph TD
    Start(["climbStairs(n)"]) --> Base["n <= 2?"]
    Base -->|Yes| ReturnN["Return n"]
    Base -->|No| MemoCheck["Already in memo?"]
    MemoCheck -->|Yes| ReturnMemo["Return memo[n]"]
    MemoCheck -->|No| Recurse["climbStairs(n-1) + climbStairs(n-2)"]
    Recurse --> Store["Store result in memo[n]"]
    Store --> ReturnMemo

function climbStairs(n, memo = {}) {
    if (n <= 2) return n; // base case for smallest inputs

    if (n in memo) return memo[n]; // reuse a result already computed

    // reduce n by 1 and 2, combine the two smaller answers
    memo[n] = climbStairs(n - 1, memo) + climbStairs(n - 2, memo);
    return memo[n];
}

from functools import lru_cache

@lru_cache(maxsize=None)
def climb_stairs(n):
    if n <= 2:
        return n  # base case for smallest inputs

    # the decorator caches every argument, so the body
    # is just the base case plus the recursive definition
    return climb_stairs(n - 1) + climb_stairs(n - 2)

class Solution {
    private int[] memo;

    public int climbStairs(int n) {
        memo = new int[n + 1];
        java.util.Arrays.fill(memo, -1); // -1 means "not computed yet"
        return helper(n);
    }

    private int helper(int n) {
        if (n <= 2) return n; // base case

        if (memo[n] != -1) return memo[n]; // reuse cached result

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

class Solution {
private:
    vector<int> memo;

public:
    int climbStairs(int n) {
        memo.assign(n + 1, -1); // -1 means "not computed yet"
        return helper(n);
    }

private:
    int helper(int n) {
        if (n <= 2) return n; // base case

        if (memo[n] != -1) return memo[n]; // reuse cached result

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

The recursion is identical in all six languages. Only the cache storage differs: an array sized n + 1 with a -1 sentinel in Java and C++ because the index is the problem size, and a hash map in the others because string-based keys or sparse lookups suit them better.

Templates only help if you can recall them without staring at the screen. Turn these snippets into flashcards for daily mobile review.

Code Breakdown

Key Variables

n: the argument each call reduces toward the base case.
memo: the cache. In Java and C++ it is an array where index equals argument value; in the other languages it is a hash map.
helper / code: a private function in Java and C++ that hides the memo from the public API. Go and Ruby pass the memo explicitly instead.

Critical Sections

Check the memo before recursing. If the cache is checked after the recursive calls, the forcing of cache hits is lost because the recursion happens first. In every language here the order is the same: base case, cache check, recurse, store.

Store before returning. The store line is what makes sibling branches cheap. Write the memo for n before returning from each call, otherwise the branch that calls climbStairs(n) again recomputes the whole subtree.

Shrink the input in the recursive case. If the recursive call does not reduce n, the base case is never reached and the stack overflows. Each call must move strictly closer to the base case.

Variation: Tree Recursion

When the input is not a number but a tree, the recursion descends into child nodes instead of subtracting from a counter. The base case is the null node; the recursive case calls the function on the left and right children and combines the two answers.

Use for Maximum Depth of Binary Tree .

function maxDepth(root) {
    if (!root) return 0; // missing node contributes no height

    // the height of this node is 1 plus the taller child
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

The structure is the memoized template with the memo removed and the argument changed from an integer to a node. If the problem asks for a count, the combine step is a sum or max. If it asks whether a property holds, the combine step becomes a boolean, such as and for “all children satisfy it”.

Complexity	Value
Time	O(N)
Space	O(H)

Time is O(N) because each node is visited once. Space is O(H) where H is the height of the tree, because the call stack holds one frame per level. A one-sided tree degrades this to O(N).

Variation: Backtracking with a choices List

When the problem requires exploring every combination, the recursion loops over the available choices, adds one choice, recurses, then undoes the choice. The base case is not a value but a condition, such as the path being complete.

Use for Subsets and combination problems.

    graph TD
    Start(["backtrack(start, path)"]) --> Record["Record path as a solution"]
    Record --> Loop{"Choices remaining?"}
    Loop -->|Yes| Take["Take choice i"]
    Take --> Recurse["backtrack(i+1, path)"]
    Recurse --> Undo["Undo choice i (pop)"]
    Undo --> Loop
    Loop -->|No| Done["Return"]

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

    function backtrack(start, path) {
        result.push([...path]); // every path ending here is a subset

        for (let i = start; i < nums.length; i++) {
            path.push(nums[i]);    // take this choice
            backtrack(i + 1, path); // explore all subsets built on it
            path.pop();            // undo it so the next choice starts clean
        }
    }

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

def subsets(nums):
    result = []

    def backtrack(start, path):
        result.append(path[:])  # copy: the original path gets mutated later

        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result

class Solution {
    List<List<Integer>> result;

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

    private void backtrack(int[] nums, int start, List<Integer> path) {
        result.add(new ArrayList<>(path)); // deep copy; the list is reused

        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtrack(nums, i + 1, path);
            path.remove(path.size() - 1);
        }
    }
}

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> path;
        backtrack(nums, 0, path, result);
        return result;
    }

private:
    void backtrack(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& result) {
        result.push_back(path); // push copies the path, safe to mutate

        for (int i = start; i < nums.size(); i++) {
            path.push_back(nums[i]);
            backtrack(nums, i + 1, path, result);
            path.pop_back();
        }
    }
};

func subsets(nums []int) [][]int {
    result := [][]int{}
    var path []int

    var backtrack func(int)
    backtrack = func(start int) {
        pathCopy := make([]int, len(path))
        copy(pathCopy, path) // snapshot, path is reused below
        result = append(result, pathCopy)

        for i := start; i < len(nums); i++ {
            path = append(path, nums[i])
            backtrack(i + 1)
            path = path[:len(path)-1]
        }
    }

    backtrack(0)
    return result
}

def subsets(nums, start = 0, path = [])
  result = []
  result << path.dup # snapshot before the array is reused

  (start...nums.length).each do |i|
    path << nums[i]
    result.concat(subsets(nums, i + 1, path))
    path.pop
  end

  result
end

The critical detail in every language is copying the path before recording it. The path array is shared and mutated for the rest of the exploration. If you store the reference instead of a copy, later pops corrupt every recorded answer. The push, recurse, pop trio is the whole skeleton. Removing the pop produces wrong answers that double-count the same prefix forever.

    flowchart LR
    A[Push choice] --> B[Recurse deeper] --> C[Pop choice] --> A

Time

O(2^N)

| Space

O(N)

for the call stack.

Variation: Top-Down Accumulation

When a path, not a final value, carries the information needed, the recursion pushes the running value down into the child calls rather than combining bottom-up. The base case receives the accumulated value and reports whether it satisfies the constraint.

def has_path_sum(root, target):
    # pass the remainder down each branch; it shrinks on the way down,
    # and the leaves check whether it hit zero exactly
    def walk(node, remaining):
        if not node:
            return False
        remaining -= node.val
        if not node.left and not node.right:
            return remaining == 0
        return walk(node.left, remaining) or walk(node.right, remaining)

    return walk(root, target)

The combine step, instead of summing subtrees, is an or across the children. Each leaf reports whether its own path hit the target, and the or propagates the earliest true answer up. The stack cost matches the tree recursion case: O(H).

Each variation above becomes a separate review card in the app. Drill them individually so you do not mix up base cases under pressure.

Applying These Templates

The practice problems put each template to work. Fibonacci Number and Climbing Stairs run the memoized template, K-th Symbol in Grammar strips the memo for pure tail recursion, Decode String adds position tracking, Different Ways to Add Parentheses forks on operators, and Wildcard Matching combines memoization with a two-dimensional key.

Now that you have the templates, the next step is application. Head to the practice problems or start reviewing these templates with spaced repetition .