Recursion: Practice Problems with Solutions

Coding Patterns - Guide to 30 Core Algorithm Patterns

Recursion: Complete Guide to Base Cases and Memoization

Welcome to the recursion practice set. If the code templates are not fresh in your head yet, review them first. Each problem below has a hint, a diagram, and the full solution in six languages. During an interview the hard part of recursion is discovering the base case and the subproblem, so the hints focus on that.

Recommended Study Order

The problems are ordered to build one skill before the next.

Fibonacci Number is the entry point. The subproblem is the problem at a smaller argument, and memoization shows up immediately.
Climbing Stairs is the same recurrence wearing a word problem disguise. If you see why climbing and Fibonacci are the same animal, the recognition skill works.
K-th Symbol in Grammar throws away the whole tree. You never build all of row N. You narrow one position at a time, which is recursion at its leanest.
Decode String adds a parser. The recursive case sits inside a loop and returns two things at once, the decoded text and the position where the caller should continue.
Different Ways to Add Parentheses splits the input on operators and combines results from both halves. This is recursion over a structure, not over a counter.
Wildcard Matching combines recursion with memoization over two strings. It is the hardest because the memo key is two indices and the base cases must handle whichever string runs out first.

The order above is designed to build intuition progressively. The app schedules your reviews so you do not forget the Easy patterns while grinding Hard ones. Set up your review schedule .

Easy Problems

1. Fibonacci Number

LeetCode 509 | Difficulty: Easy

Return the n-th Fibonacci number, where F(0) = 0 and F(1) = 1. Every other value is the sum of the two previous ones.

Why this pattern: the definition is the base case plus the recursive case, with no translation needed. F(n) = F(n-1) + F(n-2) reads as “solve the same function on smaller inputs and combine the results.”

Key Insight: naive recursion recomputes the same arguments many times. The memo turns an exponential tree into a linear chain, because every distinct argument gets computed once.

Visual:

    graph LR
    A["F(5)"] --> B["F(4)"]
    A --> C["F(3)"]
    B --> D["F(3) again"]
    B --> E["F(2)"]
    D -.-> F["memo returns instantly"]
    E -.-> G["memo returns instantly"]

Code:

var fib = function(n, memo = {}) {
    if (n <= 1) return n; // base case

    if (n in memo) return memo[n]; // reuse an earlier result

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

from functools import lru_cache

class Solution:
    @lru_cache(maxsize=None)
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        # the decorator caches every argument pair, so
        # each smaller call is evaluated once
        return self.fib(n - 1) + self.fib(n - 2)

class Solution {
    private int[] memo;

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

    private int helper(int n) {
        if (n <= 1) return n;

        if (memo[n] != -1) return memo[n];

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

The memo cache turns the tree into one path through all N arguments. In Java and C++ it is an array indexed by n, with -1 as the “not computed” sentinel. In the other languages it is a hash map passed along with the argument. The rest of the template stays identical across all six.

Time:

O(N)

| Space:

O(N)

2. Climbing Stairs

LeetCode 70 | Difficulty: Easy

You climb a staircase of N steps, taking either 1 or 2 steps at a time. Return the number of distinct ways to reach the top.

Why this pattern: the decision “1 step or 2 steps” splits the problem into two smaller instances of itself, ways(n-1) and ways(n-2). The count for N is the sum of the counts for the two smaller values.

Key Insight: this is Fibonacci in a story costume, but the base case differs. ways(1) = 1, ways(2) = 2, and every larger value is the sum of the two previous ones. Trace n = 1 and n = 2 on paper before writing the recursive case.

Visual:

    graph TD
    A["5 stairs"] --> B["4 stairs"]
    A --> C["3 stairs"]
    B --> D["3 stairs again"]
    B --> E["2 stairs = 2"]
    C --> F["2 stairs = 2"]
    C --> G["1 stair = 1"]
    D -.-> H["memo hit"]

Code:

var climbStairs = function(n, memo = {}) {
    if (n <= 2) return n; // 1 stair has 1 way, 2 stairs have 2

    if (n in memo) return memo[n];

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

from functools import lru_cache

class Solution:
    @lru_cache(maxsize=None)
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n

        return self.climbStairs(n - 1) + self.climbStairs(n - 2)

This is the memoized template from the first problem almost line for line. The only change is the base case. If you solved Fibonacci first, you should have been able to type this one without looking. Spotting the shared recurrence is the whole interview signal.

Time:

O(N)

| Space:

O(N)

Medium Problems

3. K-th Symbol in Grammar

LeetCode 779 | Difficulty: Medium

Row 1 is 0. Each later row takes the previous row and appends its inverted copy, where 0 becomes 1 and 1 becomes 0. Return the K-th character of row N, with K counted from 1.

Why this pattern: the row is a recursive description. Row N contains row N-1 as its left half and the inverted row N-1 as its right half. The recursion halves the search space and follows one path down instead of building the whole row.

Key insight: if K is in the left half, the answer is the K-th symbol of row N-1. If K is in the right half, the answer is the complement of the symbol at K - half.

Visual:

    graph LR
    A["Row 1: 0"] --> B["Row 2: 0 1"]
    B --> C["Row 3: 0 1 1 0"]
    C --> D["Row 4: 0 1 1 0 1 0 0 1"]

Code:

var kthGrammar = function(n, k) {
    if (n === 1) return 0; // the base row is "0"

    // row N is row N-1 (left half) followed by its complement (right half)
    const half = 1 << (n - 2);
    if (k <= half) {
        return kthGrammar(n - 1, k);        // same index, left half
    }
    return 1 - kthGrammar(n - 1, k - half); // flipped symbol, right half
};

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        if n == 1:
            return 0

        half = 1 << (n - 2)  # length of row n-1
        if k <= half:
            return self.kthGrammar(n - 1, k)
        return 1 - self.kthGrammar(n - 1, k - half)

The recursion descends one path through the row tree, so the work is linear in N. The 1 - result trick turns a branch into math: each jump into the right half flips the answer once, and the parity of jumps produces the final bit.

Time:

O(N)

| Space:

O(N)

4. Decode String

LeetCode 394 | Difficulty: Medium

Given an encoded string like 3[a2[c]], decode it to accaccacc. The encoding is count[encoded_string], and groups can nest.

Why this pattern: every opening bracket starts a complete, independent decoding problem. The recursion needs to return two things to the caller: the decoded text and the position where the caller should continue.

Key insight: return both at once. Then the caller knows where the inner group ended without rescanning it.

Visual:

    graph TD
    A["position 0: '3'"] --> B["position 1: '['"]
    B --> C["decode inside: a 2 [ c ]"]
    C --> D["inner 'acc', continue after ]"]
    D --> E["repeat 'acc' 3 times"]
    E --> F["accaccacc"]

Code:

var decodeString = function(s) {
    let pos = 0;

    function read() {
        let out = "";
        let count = 0;

        while (pos < s.length) {
            const ch = s[pos];

            if (ch >= "0" && ch <= "9") {
                count = count * 10 + Number(ch);
            } else if (ch === "[") {
                pos++;
                const inner = read();         // decode the child group
                out += inner.repeat(count);   // apply this level's count
                count = 0;
            } else if (ch === "]") {
                return out;                   // this group ends here
            } else {
                out += ch;                    // plain character
            }
            pos++;
        }

        return out;
    }

    return read();
};

class Solution:
    def decodeString(self, s: str) -> str:
        pos = 0

        def read():
            nonlocal pos
            out = []
            count = 0

            while pos < len(s):
                ch = s[pos]
                if ch.isdigit():
                    count = count * 10 + int(ch)
                elif ch == "[":
                    pos += 1
                    out.append(read() * count)  # child group handles itself
                    count = 0
                elif ch == "]":
                    return "".join(out)
                else:
                    out.append(ch)
                pos += 1

            return "".join(out)

        return read()

class Solution {
    int pos = 0;

    public String decodeString(String s) {
        return read(s);
    }

    private String read(String s) {
        StringBuilder out = new StringBuilder();
        int count = 0;

        while (pos < s.length()) {
            char c = s.charAt(pos);

            if (Character.isDigit(c)) {
                count = count * 10 + (c - '0');
            } else if (c == '[') {
                pos++;                     // step past the bracket
                String inner = read(s);    // decode the child group
                out.append(inner.repeat(count));
                count = 0;
            } else if (c == ']') {
                return out.toString();     // this group ends here
            } else {
                out.append(c);
            }
            pos++;
        }

        return out.toString();
    }
}

class Solution {
private:
    int pos = 0;

public:
    string decodeString(const string& s) {
        return read(s);
    }

    string read(const string& s) {
        string out;
        int count = 0;

        while (pos < (int)s.size()) {
            char c = s[pos];

            if (isdigit(c)) {
                count = count * 10 + (c - '0');
            } else if (c == '[') {
                pos++;
                string inner = read(s);
                while (count--) out += inner;
                count = 0;
            } else if (c == ']') {
                return out;
            } else {
                out += c;
            }
            pos++;
        }

        return out;
    }
};

func decodeString(s string) string {
    pos := 0

    var read func() string
    read = func() string {
        var out strings.Builder
        count := 0

        for pos < len(s) {
            ch := s[pos]

            if ch >= '0' && ch <= '9' {
                count = count*10 + int(ch-'0')
            } else if ch == '[' {
                pos++
                out.WriteString(strings.Repeat(read(), count))
                count = 0
            } else if ch == ']' {
                return out.String()
            } else {
                out.WriteByte(ch)
            }
            pos++
        }

        return out.String()
    }

    return read()
}

def decode_string(s)
  pos = 0

  read = lambda do
    out = +""
    count = 0

    while pos < s.length
      ch = s[pos]

      if ch =~ /[0-9]/
        count = count * 10 + ch.to_i
      elsif ch == "["
        pos += 1
        out << read.call * count
        count = 0
      elsif ch == "]"
        return out
      else
        out << ch
      end
      pos += 1
    end

    out
  end

  read.call
end

Every character is consumed exactly once across all levels of recursion because each call returns the position where its caller should continue. The recursion depth equals the maximum nesting depth. No memo is needed: each [ opens a genuinely new substring, so there is nothing to reuse.

Time:

O(N)

| Space:

O(N)

5. Different Ways to Add Parentheses

LeetCode 241 | Difficulty: Medium

Given an expression of numbers joined by +, -, and *, return all possible results from grouping the expression in different ways.

Why this pattern: each operator splits the expression into an independent left part and right part, and each part is recursively reduced. The recursion here divides a structure: split at an operator, solve both sides, and combine every pair of answers.

Key insight: the base case is an expression with no operator, which is exactly one number. When a slice produces no operator, it is a leaf.

Visual:

    graph TD
    A["2 - 1 - 1"] --> B["split at first -"]
    B --> C["left: 2"]
    B --> D["right: 1 - 1"]
    D --> E["(1 - 1) = 0"]
    C --> F["2 - 0 = 2"]
    A --> G["split at the second -, gives 0"]

Code:

var diffWaysToCompute = function(expression) {
    const result = [];

    for (let i = 0; i < expression.length; i++) {
        const ch = expression[i];
        if (ch !== "+" && ch !== "-" && ch !== "*") continue;

        // split at the operator, shrink both sides independently
        const left = diffWaysToCompute(expression.slice(0, i));
        const right = diffWaysToCompute(expression.slice(i + 1));

        for (const l of left) {
            for (const r of right) {
                if (ch === "+") result.push(l + r);
                if (ch === "-") result.push(l - r);
                if (ch === "*") result.push(l * r);
            }
        }
    }

    // no operator found: this chunk is a single number
    if (result.length === 0) result.push(Number(expression));

    return result;
};

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        result = []

        for i, ch in enumerate(expression):
            if ch in "+-*":
                left = self.diffWaysToCompute(expression[:i])
                right = self.diffWaysToCompute(expression[i + 1:])
                for l in left:
                    for r in right:
                        if ch == "+":
                            result.append(l + r)
                        elif ch == "-":
                            result.append(l - r)
                        else:
                            result.append(l * r)

        if not result:
            result.append(int(expression))

        return result

class Solution {
    public List<Integer> diffWaysToCompute(String expression) {
        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < expression.length(); i++) {
            char ch = expression.charAt(i);
            if (ch != '+' && ch != '-' && ch != '*') continue;

            List<Integer> left = diffWaysToCompute(expression.substring(0, i));
            List<Integer> right = diffWaysToCompute(expression.substring(i + 1));

            for (int l : left) {
                for (int r : right) {
                    if (ch == '+') result.add(l + r);
                    else if (ch == '-') result.add(l - r);
                    else result.add(l * r);
                }
            }
        }

        if (result.isEmpty()) result.add(Integer.parseInt(expression));

        return result;
    }
}

class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        vector<int> result;

        for (int i = 0; i < expression.size(); i++) {
            char ch = expression[i];
            if (ch != '+' && ch != '-' && ch != '*') continue;

            vector<int> left = diffWaysToCompute(expression.substr(0, i));
            vector<int> right = diffWaysToCompute(expression.substr(i + 1));

            for (int l : left) {
                for (int r : right) {
                    if (ch == '+') result.push_back(l + r);
                    else if (ch == '-') result.push_back(l - r);
                    else result.push_back(l * r);
                }
            }
        }

        if (result.empty()) result.push_back(stoi(expression));

        return result;
    }
};

func diffWaysToCompute(expression string) []int {
    result := []int{}

    for i := 0; i < len(expression); i++ {
        ch := expression[i]
        if ch != '+' && ch != '-' && ch != '*' {
            continue
        }

        left := diffWaysToCompute(expression[:i])
        right := diffWaysToCompute(expression[i+1:])

        for _, l := range left {
            for _, r := range right {
                switch ch {
                case '+':
                    result = append(result, l+r)
                case '-':
                    result = append(result, l-r)
                case '*':
                    result = append(result, l*r)
                }
            }
        }
    }

    if len(result) == 0 {
        n, _ := strconv.Atoi(expression)
        result = append(result, n)
    }

    return result
}

def diff_ways_to_compute(expression)
  result = []

  expression.each_char.with_index do |ch, i|
    next unless ["+", "-", "*"].include?(ch)

    left = diff_ways_to_compute(expression[0...i])
    right = diff_ways_to_compute(expression[(i + 1)..])

    left.each do |l|
      right.each do |r|
        case ch
        when "+" then result << l + r
        when "-" then result << l - r
        when "*" then result << l * r
        end
      end
    end
  end

  result << expression.to_i if result.empty?

  result
end

The number of groupings is a Catalan number and the run time is exponential in the operator count, hence the red badge. The stack stays linear: each call reduces the slice before the next level.

Time:

O(4^N)

| Space:

O(N)

Hard Problems

6. Wildcard Matching

LeetCode 44 | Difficulty: Hard

Match the whole string s against the pattern p. ? matches any single character; * matches any sequence of characters, including the empty sequence.

Why this pattern: a * forces a choice at every step: consume one more character, or skip the star. That choice becomes two recursive calls, and the position pair (i, j) is the memo key.

Key insight: the base cases depend on which string runs out first. When the string is empty, only trailing stars can still match. When the pattern is empty but the string is not, nothing can match.

Visual:

    graph TD
    A["solve(0,0): s=adceb, p=*a*b"] --> B["* is a star: consume or skip"]
    B --> C["consume it: solve(1,0)"]
    B --> D["skip it: solve(0,1)"]
    C --> E["a matches a: solve(2,2)"]
    E --> F["* star again: solve(3,3) or solve(2,3)"]
    F --> G["then b matches b"]
    G --> H["true"]

Code:

var isMatch = function(s, p) {
    const memo = new Map();

    function solve(i, j) {
        const key = i + "," + j;
        if (memo.has(key)) return memo.get(key);

        let answer;
        if (i === s.length) {
            // the string is spent: only stars can still match
            answer = true;
            for (let x = j; x < p.length; x++) {
                if (p[x] !== "*") answer = false;
            }
        } else if (j === p.length) {
            answer = false; // pattern spent, string not
        } else if (p[j] === "*") {
            answer = solve(i + 1, j) || solve(i, j + 1);
        } else if (p[j] === "?" || p[j] === s[i]) {
            answer = solve(i + 1, j + 1);
        } else {
            answer = false;
        }

        memo.set(key, answer);
        return answer;
    }

    return solve(0, 0);
};

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        memo = {}

        def solve(i, j):
            key = (i, j)
            if key in memo:
                return memo[key]

            if i == len(s):
                answer = all(c == "*" for c in p[j:])
            elif j == len(p):
                answer = False
            elif p[j] == "*":
                answer = solve(i + 1, j) or solve(i, j + 1)
            elif p[j] == "?" or p[j] == s[i]:
                answer = solve(i + 1, j + 1)
            else:
                answer = False

            memo[key] = answer
            return answer

        return solve(0, 0)

class Solution {
    private Boolean[][] memo;

    public boolean isMatch(String s, String p) {
        memo = new Boolean[s.length() + 1][p.length() + 1];
        return solve(s, p, 0, 0);
    }

    private boolean solve(String s, String p, int i, int j) {
        if (memo[i][j] != null) return memo[i][j];

        boolean answer;
        if (i == s.length()) {
            answer = true;
            for (int x = j; x < p.length(); x++) {
                if (p.charAt(x) != '*') answer = false;
            }
        } else if (j == p.length()) {
            answer = false;
        } else if (p.charAt(j) == '*') {
            answer = solve(s, p, i + 1, j) || solve(s, p, i, j + 1);
        } else if (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i)) {
            answer = solve(s, p, i + 1, j + 1);
        } else {
            answer = false;
        }

        memo[i][j] = answer;
        return answer;
    }
}

class Solution {
private:
    vector<vector<int>> memo;

public:
    bool isMatch(string s, string p) {
        memo.assign(s.size() + 1, vector<int>(p.size() + 1, -1));
        return solve(s, p, 0, 0) == 1;
    }

private:
    int solve(string& s, string& p, int i, int j) {
        if (memo[i][j] != -1) return memo[i][j];

        bool answer;
        if (i == s.size()) {
            answer = true;
            for (int x = j; x < p.size(); x++) {
                if (p[x] != '*') answer = false;
            }
        } else if (j == p.size()) {
            answer = false;
        } else if (p[j] == '*') {
            answer = solve(s, p, i + 1, j) || solve(s, p, i, j + 1);
        } else if (p[j] == '?' || p[j] == s[i]) {
            answer = solve(s, p, i + 1, j + 1);
        } else {
            answer = false;
        }

        memo[i][j] = answer ? 1 : 0;
        return memo[i][j];
    }
};

func isMatch(s string, p string) bool {
    memo := make(map[[2]int]bool)

    var solve func(i, j int) bool
    solve = func(i, j int) bool {
        key := [2]int{i, j}
        if val, exists := memo[key]; exists {
            return val
        }

        var answer bool
        if i == len(s) {
            answer = true
            for x := j; x < len(p); x++ {
                if p[x] != '*' {
                    answer = false
                }
            }
        } else if j == len(p) {
            answer = false
        } else if p[j] == '*' {
            answer = solve(i+1, j) || solve(i, j+1)
        } else if p[j] == '?' || p[j] == s[i] {
            answer = solve(i+1, j+1)
        } else {
            answer = false
        }

        memo[key] = answer
        return answer
    }

    return solve(0, 0)
}

def is_match(s, p)
  memo = {}

  solve = lambda do |i, j|
    key = [i, j]
    return memo[key] if memo.key?(key)

    if i == s.length
      answer = p[j..].chars.all? { |c| c == "*" }
    elsif j == p.length
      answer = false
    elsif p[j] == "*"
      answer = solve.call(i + 1, j) || solve.call(i, j + 1)
    elsif p[j] == "?" || p[j] == s[i]
      answer = solve.call(i + 1, j + 1)
    else
      answer = false
    end

    memo[key] = answer
    answer
  end

  solve.call(0, 0)
end

Each (i, j) pair is visited once, so time is the product of the two string sizes. Without memo this degenerates to huge recomputation. The stack alone would be O(N + M), but the memo dominates. The shift from the earlier problems is the key shape: a scalar position became a coordinate, and more of the function became base handling plus memo lookup.

Time:

O(N*M)

| Space:

O(N*M)

These six problems cover the full arc of recursive thinking. The Easy pair locks in the memoization template. The Medium problems teach recursion as classifier, parser, and splitter. The Hard problem applies the same template to a two-dimensional key. If you want the backtracking branch of recursion, subsets and permutations live on the backtracking problems page , which is the same skeleton with an explicit undo step.

Done with these problems? The app has more, and its spaced repetition system brings recursion problems back right before you would forget the pattern. Continue your prep .