Question

Given non-negative integers x and n, x taken to the nth power can be defined as: x to the 0th power is 1 x to the nth power can be obtained by multiplying x to the n-1'th power with x Write a long-valued function named power that accepts two int parameters x and n (in that order) and recursively calculates and returns the value of x taken to the n'th power.

Answer 1

Answer:

The power function can be written as a recursive function (using Java) as follows:

1. static int power(int x, int n)
2. {
3.        if(n == 0){
4.            return 1;
5.        }
6.        else {
7.            return power(x, n-1 ) * x;
8.        }
9. }

Explanation:

A recursive function is a function that call itself during run time.

Based on the question, we know x to the 0th power is 1. Hence, we can just create a condition if n = 0, return 1 (Line 3 - 5).

Next, we  implement the logic "x to the nth power can be obtained by multiplying x to the n-1'th power with x " from the question with the code:  return power(x, n-1 ) * x in the else block. (Line 6 -8)

In Line 7, power() function will call itself recursively by passing x and n-1 as arguments. Please note the value of n will be reduced by one for every round of recursive call. This recursive call will stop when n = 0.

Just imagine if we call the function as follows:

int result =  power(2,  3);

What happen  will be as follows:

• run Line 7 -> return power(2, 2) * 2    
• run Line 7 -> return power(2, 1) * 2
• run Line 7 -> return power(1, 0) * 2
• run Line 4 -> return 1    (Recursive call stop here)

Next, the return value from the inner most recursive call will be return to the previous call stack:

• power(1, 0) * 2   ->   1 * 2
• power(2, 1) * 2   ->   1 * 2 * 2
• power(2, 2) * 2   ->   1 * 2 * 2 * 2 - > 8 (final output)