The following recursive function will print the nth power of 2. def powerOf2(n): if n == 0: return 1 else: return (2 * powerOf2(n - 1))

Answer 1

The recursive function you provided correctly computes the \( n \)-th power of 2. Let's break it down step by step:

Code Explanation

def powerOf2(n):
    if n == 0:
        return 1
    else:
        return 2 * powerOf2(n - 1)

1. Base Case: The function checks if \( n \) is 0. If it is, it returns 1. This is because \( 2^0 = 1 \).

2. Recursive Case: If \( n \) is not 0, the function calls itself with \( n - 1 \) and multiplies the result by 2. This effectively builds up the power of 2 as it unwinds the recursion.

Example Outputs

• powerOf2(0) would return 1 (since \( 2^0 = 1 \)).
• powerOf2(1) would return 2 (since \( 2^1 = 2 \)).
• powerOf2(2) would return 4 (since \( 2^2 = 4 \)).
• powerOf2(3) would return 8 (since \( 2^3 = 8 \)).
• powerOf2(4) would return 16 (since \( 2^4 = 16 \)).

Performance Considerations

• Time Complexity: The time complexity of this function is \( O(n) \) because it makes \( n \) recursive calls.
• Space Complexity: The space complexity is also \( O(n) \) due to the call stack used for the recursion.

Example of Usage

You can use the function like this:

n = 5
result = powerOf2(n)
print(f"2^{n} = {result}")  # Outputs: 2^5 = 32

This function is a clear illustration of recursion in computing powers, albeit there are more efficient ways (like using exponentiation by squaring) to compute powers without deep recursion.