Recursion Pruning (Return Early)

Recursion pruning returns early when a partial computation cannot beat the best answer found so far—common in branch-and-bound for optimization.

Why this shows up in the real world

Branch-and-bound for TSP relaxations; alpha-beta style cutoffs in game trees (conceptually).

Core idea (explained for students)

Pass best_so_far by reference (list wrapper or nonlocal) and compare partial cost lower bounds before expanding.

Try this in Python

def min_path_sum(grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])
    big = 10**18
    dp = [[big] * n for _ in range(m)]
    dp[0][0] = grid[0][0]
    for i in range(m):
        for j in range(n):
            if i:
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + grid[i][j])
            if j:
                dp[i][j] = min(dp[i][j], dp[i][j - 1] + grid[i][j])
    return dp[-1][-1]


print(min_path_sum([[1, 3, 1], [1, 5, 1], [4, 2, 1]]))

Common mistakes

• Pruning based on optimistic bound that is not admissible—drops optimal.
• Integer vs float tolerance in bounds.

Key takeaways

• Prove bound admissible (never overestimates minimization lower bound).
• Log best updates to verify monotonic improvement.