A human pyramid is a way of stacking people vertically in a triangle. With the exception of the people in the bottom row, each person splits their weight evenly on the two people below them in the pyramid. For example, in the pyramid to the right, person A splits her weight across people B and C, and person H splits his weight plus the accumulated weight of the people hes supporting onto people L and M. It can be mighty uncomfortable to be in the bottom row, since you'll have a lot of weight on your back! In this question, you'll explore just how much weight that is. For this example we will use nice round numbers here, let's assume that everyone in the pyramid weighs exactly 200 pounds.

Person A at the top of the pyramid has no weight on her back. People B and C are each carrying half of person A's weight. That means that each of them are shouldering 100 pounds. Slightly uncomfortable, but not too bad.

Now, let's look at the people in the third row. Lets begin by focusing on person E. How much weight is she supporting? Well, shes directly supporting half the weight of person B (100 pounds) and half the weight of person E (100 pounds), so shes supporting at least 200 pounds. On top of this, shes feeling some of the weight that people B and C are carrying. Half of the weight that person B is shouldering (50 pounds) gets transmitted down onto person E and half the weight that person C is shouldering (50 pounds) similarly gets sent down to person E, so person E ends up feeling an extra 100 pounds. That means shes supporting a net total of 300 pounds. Thats going to be noticeable!

Not everyone in that third row is feeling the same amount, though. Look at person D for example. The only weight on person D comes from person B. Person D therefore ends up supporting

• half of person Bs body weight (100 pounds), plus
• half of the weight person B is holding up (50 pounds),

so person D ends up supporting 150 pounds, only half of what E is feeling! Going deeper in the pyramid, how much weight is person H feeling? Well, person H is supporting

• half of person Ds body weight (100 pounds),
• half of person Es body weight (100 pounds), plus
• half of the weight person D is holding up (75 pounds), plus
• half of the weight person E is holding up (150) pounds.

The net effect is that person H is carrying 425 pounds ouch! A similar calculation shows that person I is also carrying 425 pounds can you see why? Compare this to person G. Person G is supporting

• half of person Ds body weight (100 pounds), plus
• half of the weight person D is holding up (75 pounds)

for a net total of 175 pounds. Thats a lot, but its not nearly as bad as what person H is feeling! Finally, lets look at poor person M in the middle of the bottom row. How is she doing? Well, shes supporting

• half of person Hs body weight (100 pounds),
• half of person Is body weight (100 pounds),
• half of the weight person H is holding up (212.5 pounds), and
• half of the weight person I is holding up (215.5 pounds),

for a net total of 625 pounds. Yikes! No wonder she looks so unhappy.

As we can see that there's a nice, general pattern here that lets us compute how much weight is on each person's back:

Using this general pattern, write a recursive function

double weightOnBackOf(int row, int col);

that takes as input the row and column number of a person in a human pyramid, then returns the total weight on that person's back. The row and column are each zero-indexed, so the person at row 0, column 0 is on top of the pyramid, and person M in the above picture is at row 4, column 2. So if we look at the above example, weightOnBackOf(1, 1) would return 100 pounds (since person C is shouldering 100 pounds on her back), and weightOnBackOf(4, 2) should return 625 (since person M is shouldering a whopping 625 pounds on her back).

Your implementation of weightOnBackOf must be implemented recursively and must not use any loops (for, while, or do ... while). I hope that you'll be pleasantly surprised how little code is required!

Your program will ask for a weight for the humans in your human pyramid . You can assume that all humans in the pyramid (like in the example above everyone weighs 200lbs) will

be that weight .

You should test for up to 5 rows. If it works for five it will work for an infinite number of rows and columns.

NOTE: MUST be in Java and MUST use RECURSION.

Please add comments to your program!