Introduction

The recursive coin-change problem is a classic example of how an elegant-looking algorithm can hide a very expensive time complexity. The recursive version repeatedly explores the same subproblems, which makes it a useful teaching example for why memoization and dynamic programming matter.

The exact complexity depends on which coin-change variant you mean, but the common naive recursive approach is exponential. That is the key result most people are trying to understand when they ask about coin-change recursion.

The Naive Recursive Version

Suppose you want the minimum number of coins needed to make a target amount. A straightforward recursive function tries every coin and recursively solves the smaller remaining amount.

1def min_coins(amount, coins):
2    if amount == 0:
3        return 0
4    if amount < 0:
5        return float("inf")
6
7    best = float("inf")
8    for coin in coins:
9        candidate = min_coins(amount - coin, coins)
10        best = min(best, candidate + 1)
11
12    return best
13
14
15coins = [1, 3, 4]
16amount = 6
17answer = min_coins(amount, coins)
18print(answer if answer != float("inf") else -1)

This code is correct for small inputs, but it recomputes the same amounts again and again. For example, if the function evaluates amount 6, it may reach amount 3 through several different paths and solve it from scratch every time.

Why the Time Complexity Blows Up

At each amount, the function branches across all coin choices. If there are n coin denominations and the recursion can go as deep as the target amount A, the recursion tree can grow roughly like n^A in the worst case.

That is not a tight mathematical bound for every coin system, but it captures the important truth: the naive recursion is exponential. The repeated subproblems are what make it so expensive.

You can see the overlap with a tiny example:

• 'min_coins(6) may call min_coins(5), min_coins(3), and min_coins(2)'
• 'min_coins(5) may also call min_coins(4), min_coins(2), and min_coins(1)'
• 'min_coins(3) may call min_coins(2) again'

The amount 2 appears repeatedly. The recursive algorithm treats each appearance as a new problem even though the answer is identical every time.

Memoization Changes the Cost Completely

Once you cache the answer for each amount, every subproblem is solved once instead of many times.

1def min_coins_memo(amount, coins, memo=None):
2    if memo is None:
3        memo = {}
4
5    if amount == 0:
6        return 0
7    if amount < 0:
8        return float("inf")
9    if amount in memo:
10        return memo[amount]
11
12    best = float("inf")
13    for coin in coins:
14        candidate = min_coins_memo(amount - coin, coins, memo)
15        best = min(best, candidate + 1)
16
17    memo[amount] = best
18    return best
19
20
21print(min_coins_memo(6, [1, 3, 4]))

Now there are only A + 1 meaningful subproblems, from 0 through A. For each amount, you try n coins. That makes the time complexity O(A * n) and the memo size O(A).

Bottom-Up Dynamic Programming

The same complexity can be reached iteratively with bottom-up dynamic programming:

1def min_coins_dp(amount, coins):
2    dp = [float("inf")] * (amount + 1)
3    dp[0] = 0
4
5    for current in range(1, amount + 1):
6        for coin in coins:
7            if current - coin >= 0:
8                dp[current] = min(dp[current], dp[current - coin] + 1)
9
10    return dp[amount] if dp[amount] != float("inf") else -1
11
12
13print(min_coins_dp(6, [1, 3, 4]))

This avoids recursion depth concerns and is usually the practical implementation for production code.

Common Pitfalls

• Calling the naive recursion "polynomial" because each call looks small. The branching tree makes it exponential.
• Ignoring overlapping subproblems. That is the whole reason memoization helps so much.
• Confusing the minimum-coins problem with the number-of-ways problem. They are related but not identical and use different recurrences.
• Forgetting the base cases for 0 and negative amounts, which breaks correctness.
• Using pure recursion on large amounts in Python, which can also run into recursion-depth limits.

Summary

• The naive recursive coin-change algorithm is exponential because it recomputes the same amounts many times.
• A rough worst-case intuition is that the recursion tree grows like n^A, where n is the number of coin types and A is the amount.
• Memoization reduces the complexity to O(A * n).
• Bottom-up dynamic programming reaches the same complexity without recursion.
• Coin change is a standard example of overlapping subproblems and why dynamic programming works.