Introduction

The integer partition problem asks how many ways a positive integer can be written as a sum of positive integers when order does not matter. Recursion is a natural fit because each partition choice reduces the remaining total and restricts what numbers can appear next.

What Makes Partitions Different from Combinations

For partitions, order is irrelevant:

• '4 = 3 + 1'
• '4 = 1 + 3'

These are the same partition, not two different answers.

That means a recursive algorithm must avoid generating the same sum in different orders. The usual trick is to keep the next chosen number less than or equal to the previous one.

For 4, the partitions are:

14
23 + 1
32 + 2
42 + 1 + 1
51 + 1 + 1 + 1

So the partition count of 4 is 5.

Recursive Counting with a Maximum Allowed Part

A standard recursive function is:

• 'partitions(n, max_part)'

This means "how many partitions of n are possible using numbers up to max_part?"

The recurrence is:

• skip max_part
• or use max_part at least once

That becomes:

• 'partitions(n, max_part - 1)'
• 'partitions(n - max_part, max_part)'

with these base cases:

• if n == 0, there is exactly one valid partition
• if n < 0, there are no valid partitions
• if max_part == 0 and n > 0, there are no valid partitions

Here is a direct Python implementation:

1def count_partitions(n, max_part=None):
2    if max_part is None:
3        max_part = n
4
5    if n == 0:
6        return 1
7    if n < 0 or max_part == 0:
8        return 0
9
10    return (
11        count_partitions(n, max_part - 1)
12        + count_partitions(n - max_part, max_part)
13    )
14
15
16print(count_partitions(5))

This prints 7, because 5 has seven partitions.

Add Memoization or the Recursion Gets Expensive Fast

The plain recursive version repeats the same subproblems many times. Memoization fixes that neatly:

1from functools import lru_cache
2
3
4@lru_cache(maxsize=None)
5def count_partitions(n, max_part):
6    if n == 0:
7        return 1
8    if n < 0 or max_part == 0:
9        return 0
10
11    return (
12        count_partitions(n, max_part - 1)
13        + count_partitions(n - max_part, max_part)
14    )
15
16
17print(count_partitions(50, 50))

This version still uses the same recursive idea, but it reuses results for repeated states. That turns a mathematically elegant but slow recursion into something practical for much larger inputs.

Generating the Actual Partitions

Sometimes you want the partitions themselves, not just the count. In that case, recursion can carry a partial solution:

1def generate_partitions(n, max_part=None, prefix=None):
2    if max_part is None:
3        max_part = n
4    if prefix is None:
5        prefix = []
6
7    if n == 0:
8        yield prefix
9        return
10
11    for part in range(min(max_part, n), 0, -1):
12        yield from generate_partitions(n - part, part, prefix + [part])
13
14
15for partition in generate_partitions(5):
16    print(partition)

The key detail is passing part as the next max_part. That guarantees the generated sequence stays non-increasing, so each partition appears once.

Why the Recursion Works

The recursive structure mirrors the mathematical structure of the problem. At each step, you either:

• include a candidate number
• or move on to smaller candidates

That is why partition counting is a classic teaching example for recursive decomposition. The state is small and meaningful:

• how much total remains
• the largest part you are still allowed to use

Once you define those two values clearly, the recursion becomes easy to reason about.

When to Use Dynamic Programming Instead

Recursion is great for clarity, but for very large counts, bottom-up dynamic programming can be faster and easier to control. The recursive version is still valuable because:

• it explains the combinatorial structure
• it is easy to turn into a memoized solution
• it can generate partitions naturally

So recursion is usually the best place to learn the problem, even if you later optimize it with an iterative table.

Common Pitfalls

• Counting different orders separately, which turns the problem into compositions instead of partitions.
• Forgetting the n == 0 base case, which should contribute one valid partition.
• Omitting memoization and then concluding recursion is unusably slow.
• Generating partitions without restricting the next part, which creates duplicates.
• Mixing up "count partitions" and "list partitions" as if they required the same return type.

Summary

• Integer partitions ignore order, so recursion must avoid duplicate arrangements.
• A standard state is remaining total plus maximum allowed part.
• The classic recurrence splits into "skip this part" and "use this part."
• Memoization makes recursive counting practical for much larger inputs.
• The same recursive idea can count partitions or generate the actual lists of parts.