342: Mainline

Next, note that you can arrange for recursive_power_of_2 to hand over a little less work to power_of_2 by performing one of the multiplications by 2 in recursive_power_of_2 itself, and subtracting 1 from power_of_2's argument:

int recursive_power_of_2 (int n) {
  if (n == 0)
     return 1;
    else
     return 2 * power_of_2 (n - 1);  
} 

Clearly, recursive_power_of_2 must work as long as one of the following two situations holds:

• The value of the parameter, n, is 0; in this situation, recursive_power_of_2 returns 1.
• The value of n is not 0, but power_of_2 is able to compute the power of 2 that is 1 less than the value of n.