Binary Choice Recursion (Include / Exclude)

Binary choice at each step: include current element or skip—foundation for knapsack-style thoughts, subsets, and some digit DP intuitions.

Why this shows up in the real world

Puzzle games, constraint solvers, and interview combinatorial search all share the same skeleton: build state, recurse, undo.

Core idea (explained for students)

Two recursive calls per level; depth equals number of decisions. Memoize when overlapping subproblems appear (turn into DP).

Try this in Python

def fib(n: int, memo: dict[int, int] | None = None) -> int:
    if memo is None:
        memo = {}
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]


print(fib(8))

Common mistakes

• Exponential blow-up when no memo and overlapping states.
• Incorrect base case at leaf when both children skipped incorrectly.

Key takeaways

• Recognize when state is (index, remaining_weight) → switch to table DP.
• Draw recursion DAG for small n.