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

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. }

Step-by-step 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)