Once upon a time in a kingdom far away, the king hoarded food and the people starved. His adviser recommended that the food stores be used to help the people, but the king refused. One day a small group of rebels attempted to kill the king but were stopped by the adviser. As a reward, the adviser was granted a gift by the king. The adviser asked for a few grains of wheat from the king's stores to distribute to the people. The number of grains was to be determined by
placing them on a chessboard. On the first square of the chessboard, he placed one grain of
wheat. He then placed two grains on the second square, four grains on the third square, eight grains on the fourth square, and so forth.
- Compute the total number of grains of wheat that were placed on k squares by writing a recursive method getTotalGrains(k, grains). Each time getTotalGrains is called, it "places" grains on a single square; grains is the number of grains of wheat to place on that square. If k is 1, return grains. Otherwise, make a recursive call, where k is reduced by 1 and grains is doubled. The
recursive call computes the total number of grains placed in the remaining k - 1 squares. To find the total number of grains for all k squares, add the result of the recursive call to grains and return that sum.
- Write a suitable tester class for getTotalGrains. The method should be called with a second argument of 1. You can vary the size of k, but the number may overflow when k is greater than 63.