# The White Rabbit

If you don't get the requirements right, it doesn't matter how well you do anything else. (Karl Wiegers)

Published on Thursday, 15 December 2022

Tags:

## [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)``````