Power Of Two Using Recursion

Problem Statement: Given an integer n, return true if it is a power of 2. Otherwise, return false.

Example 1:
Input: n = 2
Output: true
Explanation: 2^1 = 2

Example 2:
Input: n = 16
Output: true
Explanation: 2^4 = 16

Example 3:
Input: n = 3
Output: false

Understanding the Recursive Idea.

A number is a power of two if we can keep dividing it by 2 and eventually reach 1.

Since we reached 1, 16 is a power of two.

Now look at 12: 

12 / 2 = 6

6 / 2 = 3

3 is not divisible by 2, so we stop.

Therefore, 12 is not a power of two.

Breaking Down the Recursive Approach.

Step 1: Handle Negative Numbers and Zero.

The powers of two numbers are always positive.

1, 2, 4, 8, 16, 32....

Step 2: Base Case

Once recursive reaches 1, we know every previous division was valid. This is the stopping condition.

Step 3: Check Divisibility

A power of two must always be divisible by 2 until it reaches 1.

Example:

10 is divisible by 2

5 is divisible by 2

Step 4: Recursive Call

If the current number is even, divide it by 2 and solve the smaller problem.

C# Recursive Code Implementation.

public class Solution {
    public bool IsPowerOfTwo(int n) {
        //Step 1: Handle Negative Numbers and Zero
        if(n <= 0) return false;

        //Step 2: Base Case
        if(n == 1) return true;

        //Step 3: Check Divisibility
        if(n % 2 != 0) return false;

        //Step 4: Recursive Call
        return IsPowerOfTwo(n / 2);
    }
}

Dry Run Example: n = 16

Call 1: IsPowerOfTwo(16)

• 16 > 0
• 16 != 1
• 16 % 2 == 0

Call 2: IsPowerOfTwo(8)

• 8 > 0
• 8 != 1
• 8 % 2 == 0

Call 3: IsPowerOfTwo(4)

• 4 > 0
• 4 != 1
• 4 % 2 == 0

Call 4: IsPowerOfTwo(2)

• 2 > 0
• 2 != 1
• 2 % 2 == 0

Call 5: IsPowerOfTwo(1)

• Now all previous calls return true.
• Final Answer will also return true.

Time Complexity: Each recursive call divides n by 2, so the complexity will be O(log n)

Space Complexity: Recursive calls are stored on the call stack of maximum depth O(log n)