General bars and stars

If this isn't simply a learning exercise, then it's not necessary for you to roll your own algorithm to generate the partitions: Python's standard library already has most of what you need, in the form of the itertools.combinations function.

From Theorem 2 on the Wikipedia page you linked to, there are n+k-1 choose k-1 ways of partitioning n items into k bins, and the proof of that theorem gives an explicit correspondence between the combinations and the partitions. So all we need is (1) a way to generate those combinations, and (2) code to translate each combination to the corresponding partition. The itertools.combinations function already provides the first ingredient. For the second, each combination gives the positions of the dividers; the differences between successive divider positions (minus one) give the partition sizes. Here's the code:

import itertools

def partitions(n, k):
    for c in itertools.combinations(range(n+k-1), k-1):
        yield [b-a-1 for a, b in zip((-1,)+c, c+(n+k-1,))]

# Example usage
for p in partitions(5, 3):
    print(p)

And here's the output from running the above code.

[0, 0, 5]
[0, 1, 4]
[0, 2, 3]
[0, 3, 2]
[0, 4, 1]
[0, 5, 0]
[1, 0, 4]
[1, 1, 3]
[1, 2, 2]
[1, 3, 1]
[1, 4, 0]
[2, 0, 3]
[2, 1, 2]
[2, 2, 1]
[2, 3, 0]
[3, 0, 2]
[3, 1, 1]
[3, 2, 0]
[4, 0, 1]
[4, 1, 0]
[5, 0, 0]

Another recursive variant, using a generator function, i.e. instead of right away printing the results, it yields them one after another, to be printed by the caller.

The way to convert your loops into a recursive algorithm is as follows:

• identify the "base case": when there are no more bars, just print the stars
• for any number of stars in the first segment, recursively determine the possible partitions of the rest, and combine them

You can also turn this into an algorithm to partition arbitrary sequences into chunks:

def partition(seq, n, min_size=0):
    if n == 0:
        yield [seq]
    else:
        for i in range(min_size, len(seq) - min_size * n + 1):
            for res in partition(seq[i:], n-1, min_size):
                yield [seq[:i]] + res

Example usage:

for res in partition("*****", 2):
    print "|".join(res)

This can be solved recursively in the following approach:

#n bins, k stars,
def F(n,k):
  #n bins, k stars, list holds how many elements in current assignment
  def aux(n,k,list):
        if n == 0: #stop clause
            print list
        elif n==1: #making sure all stars are distributed
            list[0] = k
            aux(0,0,list)
        else: #"regular" recursion:
            for i in range(k+1):
                #the last bin has i stars, set them and recurse
                list[n-1] = i
                aux(n-1,k-i,list)
  aux(n,k,[0]*n)

The idea is to "guess" how many stars are in the last bin, assign them, and recurse to a smaller problem with less stars (as much that were assigned) and one less bin.

---

Note: It is easy to replace the line

print list

with any output format you desire when the number of stars in each bin is set.