Recusive functions often solve the same problem many times

 Example:

         Look at the output for  j5 < j5-x

  (Use grep)

  The call divPie(9,1,5) occurs 3 times
  So is: divPie(8,1,5) and many others !


  There is a simple technique called

         Memoization

  that can be used to speed up recursive
  

 int computedSolutions[N];

 int recusiveSolver( n )
 {
    // Memoization part 1
    if ( computedSolutions[n] already computed )
       return computedSolutions[n];

    Write the recursiveSolver code here

    // Memoization part 2
    Before you return, do:

         computedSolutions[n] = solution
 }
  

int divPie(int nPieces, int nPeople, int min, int X)
{
   // Memoization - part 1
   if ( solved[nPieces][nPeople][min] != -1 )
       return  solved[nPieces][nPeople][min];

   if ( nPeople == 1 )
   {
      return 1;                 // This person gets nPieces
   }
   else
   {
      int nTotSols = 0, nSubSols;

      for ( int i = min; i <= nPieces/nPeople; i++ )
      {
         // Give person 1: i pies, divide n-i pies among others
         nSubSols = divPie( nPieces-i, nPeople-1, i , X+1);

         nTotSols = nTotSols + nSubSols;
      }

      // Memoization - part 2
      solved[nPieces][nPeople][min] = nTotSols;

      return nTotSols;
   }
}