*Published on Thursday, 15 December 2022*

Tags: recursion2 iteration2 algorithm3 python7

## [CODE] Integer partition function in Python (recursive and iterative)

The integer partition function p(n) is the number of ways of writing n as a sum of positive integers, where the order of the summands does not matter. Let's see how to implement it recurively and iteratively.

A partition of any integer *n* is a way to write n as a sum of other integers. **The integer partition function partition(n) gives us the number of ways a positive integer n can be written as a sum of positive integers**.

```
def partition(n):
result = 0
for k in range(n+1):
result += p(n,k)
return result
```

Now we can implement **p(n,k)**, which yields the number of ways *n* can be written as a sum of *k* integers through a *recursive* or *iterative* function.

## Recursive

```
def p(n,k):
if n==0 and k==0: return 1
if k <= 0 or n<=0: return 0
return p(n-k,k)+p(n-1,k-1)
```

## Iterative

```
def p(n,k):
if n==0 and k==0: return 1
if k <= 0 or n<=0: return 0
return p(n-k,k)+p(n-1,k-1)
```