226: Mainline

Now for the recursion trick: You replace power_of_2 in recursive_power_of_2 by recursive_power_of_2 itself:

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

The new version works for two reasons:

• If the value of the parameter, n, is 0, recursive_power_of_2 returns 1.
• If the value of n is not 0, recursive_power_of_2 asks itself to compute the power of 2 for a number that is 1 less than the value of n. Then, recursive_power_of_2 may ask itself to compute the power of 2 for a number that is 2 less than the original value of n, and so on, until the recursive_power_of_2 needs to deal with only 0.

When a function, such as recursive_power_of_2, is used in its own definition, the function is said to be recursive. When a function calls itself, the function is said to recurse.

Given a positive, integer argument, there is no danger that recursive_power_of_2 will recurse forever—calling itself an infinite number of times—because eventually the argument is counted down to 0, which recursive_power_of_2 handles directly, without further recursion.