Removing Recursion

[Duncan Smith]

Hello,
         I need to make the following code more efficient, but I am
struggling to find a decent way of removing the recursive calls.  So, anyone
any suggestions (on any ways of speeding this up)?  'bins(self)' constructs
a list containing the numbers of ways of packing 0 to n = k*(N-k) items into
k bins where each bin has maximum capacity N-k.  So I'd also be grateful if
anyone knows of a better approach to this general problem.  Thanks in
advance.

Duncan Smith


import Numeric

class MyClass:
    def __init__(self, k, N):
        self.k = k
        self.N = N
        self.bin_max = N - k
        self.n = k * self.bin_max
        self.table = MyClass.build_table(self)
        self.cumulative_table = MyClass.cumulative(self)
        self.bins_dict = {}


    def build_table(self):
        table = Numeric.zeros((self.n + 1, self.k))
        table = table.astype('i')
        table[0, 0] = 1
        for i in xrange(self.k):
            table[i+1, i] = 1
        for i in xrange(self.n + 1):
            table[i, 0] = 1
        for j in xrange(1, self.k):
            for i in xrange(j+2, self.n + 1):
                table[i, j] = table[i-1, j-1] + table[i-j-1, j]

        return table


    def cumulative(self):
        cum_table = self.table * 1
        for j in xrange(1, self.k):
            cum_table[:,j] = cum_table[:,j] + cum_table[:,j-1]

        return cum_table


    def bins(self):
        out = []
        for i in xrange(self.n + 1):
            out.append(MyClass.f(self, i, self.k, self.bin_max))

        return out


    def f(self, n, k, bin_max):
        if self.bins_dict.has_key((n, k, bin_max)):
            return self.bins_dict[(n, k, bin_max)]
        else:
            combs = self.cumulative_table[n, k-1]
            if bin_max < n:
                for i in xrange(n - bin_max):
                    combs  = combs - MyClass.f(self, i, k-1, n-i)
            self.bins_dict[(n, k, bin_max)] = combs

        return  combs