Converting simple recursive method which recurses within a loop into iterative method

Question

A while back, I was working on a programming problem (CCC). I have also come across similar questions in past contests so I decided to ask about this one. The problem is basically this.

You are given n people and p pieces of pie.

n people are standing in a row.

You must distribute p pieces of pie amongst them. You go in order and each person must receive at least as many pieces as the person before them. Each person must receive at least one piece of pie and no pie may be left over.

You must return the number of possible ways to distribute the pie.

I managed to create the following recursive solution but it takes too long (more than 5 seconds) for the following inputs:

120 pieces, 20 people --> 97132873

250 pieces, 130 people--> 1844349560

My solution:

import java.io.*;

public class Main
{
  int pieces, people;
  int combinations = 0;

  public void calculate (int person, int piecesLeft, int prev)
  {
    if (person == people)
    {
        if (piecesLeft == 0)
            combinations++;              
    }
    else
    {
        for (int x = prev ; (x * (people - person)) <= piecesLeft ; x++)
        {
            calculate (person + 1, piecesLeft - x, x);
        }
    }
  }


  public static void main (String[] args) throws Exception
  {
    Main m = new Main ();
    BufferedReader in = new BufferedReader (new InputStreamReader (System.in));
    //m.pieces = Integer.parseInt (in.readLine ());
    //m.people = Integer.parseInt (in.readLine ());
    m.pieces=250;
    m.people=130;
    if (m.people == m.pieces)
        System.out.println (1);
    else if (m.people == 1)
        System.out.println (1);
    else
    {
        m.calculate (0, m.pieces, 1);
        System.out.println (m.combinations);
    }
  }
}

I found the following python solution from the unofficial solutions which from what I understand, basically creates an array of already encountered values.

visited = []
def pi(n,k,min):
if visited [n][k][min] == 0:       
    if n == k:
        visited[n][k][min] = 1
    elif k == 1:
        visited[n][k][min] = 1
    else:
        t = 0
        for i in range (min, (n / k)+1):
            t = t + pi(n-i, k-1, i)
        visited[n][k][min] = t
return visited[n][k][min]


file = open("j5.10.in", "r")
n = int(file.readline())
k = int(file.readline())

for i in range(n+1):
x = []
for j in range(k+1):
    t = []
    for kk in range(n+1):
        t.append (0)
    x.append(t)
visited.append(x)

print pi(n,k,1)

What I want to do is make an iterative solution out of either of these but am not sure how to do it. From what I understand, there may not be a huge speed difference but with even larger cases, it will allow me to avoid stack overflows.

Answer 1

The second solution is memoized ... the visited array records values which have been calculated already. A trick to convert a memoized recursion into a (sort of) iterated solution is to loop through smaller cases to fill in the memo array. You can just throw away the results for the smaller cases (they will be stored in the memo array anyway). Then when you finally calculate the one you want, it will use the memo array right away, no extra computation.

If you really want to build up an iterative solution from the ground up, you've got to figure out what previous cases you need to store in order to build up the next case. For example, to calculate factorial, with a loop, you only need to store one value in memory. In a change-making problem with coins of denominations 1, 5, and 10 cents, you would need to save only ten previous items to construct the next one. In some cases, you need to know all previous values to construct the next. Once you know that, the memory structure should be clear, then the program logic will become clear.