title: Using an array to improve the execution time of a recursive binomial distribution algorithm?
body: <p>As a beginning programmer, I recently bought the book 'Algorithms - Forth Edition' by Robert Sedgewick/Kevin Wayne and I really appreciate the exerices at the end of each chapter. However, there is one exercise (who looks quite simple) that is driving me crazy since I can't find a solution for it.</p>
  
  <p>You have to take this recursive algorithm that finds the probability of getting exactly k successes in n trials where p is the probabily of success for one event. The algorithm given is based on the recursive binomial distribution forumula.</p>
  
  <pre><code>public static double binomial(int n, int k, double p) {
      if (n == 0 &amp;&amp; k == 0)
          return 1.0;
      else if (n &lt; 0 || k &lt; 0)
          return 0.0;
      return (1 - p) * binomial(n - 1, k, p) + p * binomial(n - 1, k - 1, p);
  }
  </code></pre>
  
  <p>The goal of this exercise is to make this algorithm faster by saving computed values in an array. I already made this algorithm considerably faster by using another way of getting the binomial distribution [p(x) = nCr * p^k * (1 - p)^(n - k)] that uses an iterative method to find factorials. However, I don't understand how an array could be used to improve execution time in this context.</p>
  
  <p>Any help would be greatly appreciated!</p>
  
  <p>... and before someone asks, this is not homeworks!</p>