Using an array to improve the execution time of a recursive binomial distribution algorithm?
algorithm, arrays, java, math
Solution
The book is trying to teach you a particular programming technique called memoization, a kind of broader technique known as dynamic programming. Of course in real life knowing a closed-form solution is much better, but not in the context of solving this exercise.
Anyway, the idea is to pass a 2D array as your fourth parameter, fill it with `NaN`s initially, and check if there's a solution for the given combination of `n` and `k` in the array before computing anything. If there is, return it; if there isn't, compute it recursively, store in the array, and only then return it.
Problem
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. 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. ``` public static double binomial(int n, int k, double p) { if (n == 0 && k == 0) return 1.0; else if (n < 0 || k < 0) return 0.0; return (1 - p) * binomial(n - 1, k, p) + p * binomial(n - 1, k - 1, 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. Any help would be greatly appreciated! ... and before someone asks, this is not homeworks!