Python找零问题递归解法：递归深度超限及性能优化求助

Hey there! Let's tackle the two problems you're facing with your recursive change-making code: the slow runtime and the "maximum recursion depth exceeded" error.

Why Your Current Code Fails #

First, let's break down the root causes:

• Recursion Depth Error: Python has a default recursion depth limit (usually around 1000). When you pass a large target like n=1000, your recursive calls stack up way beyond this limit, triggering the error.
• Timeout Issues: Your pure recursive approach has exponential time complexity—you're re-solving the same subproblems thousands of times. For example, calculating the number of ways to make 1000 cents will repeat calculations for smaller amounts like 500, 250, etc., over and over.

Solution 1: Memoized Recursion (Caching Subproblems) #

We can fix both issues by adding memoization (caching the results of subproblems so we don't recompute them). This reduces the time complexity to O(n*k) (where k is the number of coin denominations) and cuts down on unnecessary recursive calls, which helps with the depth limit.

Here's the revised code using Python's functools.lru_cache decorator:

import functools

def count_change(n, coins):
    @functools.lru_cache(maxsize=None)
    def helper(remaining, coin_index):
        # Base cases
        if remaining == 0:
            return 1
        if remaining < 0 or coin_index < 0:
            return 0
        # Two choices: skip the current coin, or use it (and keep it available for reuse)
        return helper(remaining, coin_index - 1) + helper(remaining - coins[coin_index], coin_index)
    
    return helper(n, len(coins) - 1)

# Example usage
coins = [1,5,10,25]
print(count_change(1000, coins))

Key improvements here:

• We use a nested helper function with lru_cache to store results of already computed (remaining, coin_index) pairs.
• Simplified base cases (no confusing c+1 <=0 check—we just check if we've run out of coins or have a negative remaining amount).

Solution 2: Iterative Dynamic Programming (Even Better for Large n) #

If you want to completely avoid recursion (and thus eliminate the depth limit entirely), an iterative dynamic programming approach is the way to go. It's just as efficient, but avoids stack overflow issues for extremely large values of n.

Here's the DP implementation:

def count_change_dp(n, coins):
    # dp[amount] = number of ways to make 'amount' cents
    dp = [0] * (n + 1)
    dp[0] = 1  # Base case: 1 way to make 0 cents (use no coins)
    
    for coin in coins:
        # Iterate through each amount starting from the coin's value
        for amount in range(coin, n + 1):
            dp[amount] += dp[amount - coin]
    
    return dp[n]

# Example usage
coins = [1,5,10,25]
print(count_change_dp(1000, coins))

This works by building up the solution incrementally: for each coin, we update the number of ways to make every amount from the coin's value up to n, adding the ways we can make the amount minus the current coin (since we can reuse coins).

Testing Both Solutions #

Both of these approaches will handle n=1000 easily in well under 2 seconds. The iterative DP version is slightly more efficient (no function call overhead) and eliminates any recursion depth concerns entirely.

内容的提问来源于stack exchange，提问作者David Dennis