Python memoization: cache bounded states without hiding recursion depth

Operation contract

The stock-packing recurrence computes the minimum number of package sizes needed for a target amount. A call-local cached function prevents repeated evaluation of the same remaining amount. An impossible target returns negative one rather than a plausible package count; the target and package count are bounded before recursion starts.

Failure and ownership boundary

The cache lives inside one request to avoid retaining every historical target in a global cache. Recursion still has depth proportional to the target in the worst case; caching repeated states does not remove stack depth. The fixture caps target at one hundred and rejects non-positive package sizes. Java minimum coin change: reachable states and impossible totals offers another evaluation order.

Working program

from functools import lru_cache

def minimum_packages(sizes, target):
    if type(target) is not int or not 0 <= target <= 100 or not 1 <= len(sizes) <= 20:
        raise ValueError("packing bounds")
    if any(type(size) is not int or size <= 0 for size in sizes):
        raise ValueError("positive package sizes required")
    unreachable = target + 1
    @lru_cache(maxsize=None)
    def solve(remaining):
        if remaining == 0:
            return 0
        return min((1 + solve(remaining - size) for size in sizes if size <= remaining), default=unreachable)
    answer = solve(target)
    return -1 if answer >= unreachable else answer

print(minimum_packages((3, 5), 11))
print(minimum_packages((4, 6), 7))

Output

3
-1

Costs and limits

For t bounded target states and c package sizes, recurrence work is O(t*c) and cache/stack storage is O(t), ignoring integer digit costs. The declared depth cap is part of this recursive implementation.

Common Mistakes

• Caching does not remove recursion depth.
• Do not let a global unbounded cache retain every historical request.

Connected lessons

Python closures: capture loop values at the intended time, Python functions: define units, validate input and return a result, Java minimum coin change: reachable states and impossible totals.

Apply this boundary

Python longest common subsequence: rolling-row DP and its limits, Python 0/1 knapsack: descending capacity prevents item reuse.

Follow the related contract

Python lru_cache: bound retention and include the revision in the key.