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.

Question

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 be distributed to the people. The number of grains were 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.

This demonstrates a recursion where a partial solution is being built up on the way down the recursion. What makes this interesting is that it is not just a tail recursion (the partial solution becomes the complete solution at the bottom of the recursive chain), but that it computes an answer using each of the partial solutions.

Answer 1

See the code in Grain.java.