Question

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
```python
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:

```python
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.