Power of Two: Recursion, One Halving at a Time

A power of two is a number you can reach by starting at 1 and doubling: 1, 2, 4, 8, 16, 32, and so on. The question "is this number a power of two?" sounds like it needs a math trick, but it hides one of the cleanest recursion drills you'll ever write.

The reframe is simple: if a number is a power of two, cutting it in half gives you a smaller power of two. Keep halving and you always land on 1. If you ever hit an odd number that isn't 1, you fell off the chain — it was never a power of two.

That "shrink the input until it's trivial" move is the whole shape of recursion. Get it here and the same skeleton carries into factorials, tree traversals, and every divide-and-conquer algorithm you'll meet later.

The problem#

Given a positive integer n, return true if n is a power of two, and false otherwise. A number is a power of two when it equals 2^k for some non-negative integer k — so 1 (2^0), 2 (2^1), 4 (2^2), 16 (2^4) all qualify, but 6, 10, and 12 do not.

Two facts about powers of two drive everything below:

• 1 is a power of two (2^0). It's the bottom of every halving chain, so it's the base case.
• Every power of two above 1 is even, and half of it is also a power of two. An odd number greater than 1 can never be one.

The brute force baseline#

The direct approach counts up the powers of two until you meet or pass n:

This works and it's O(log n), so it isn't even slow. But it walks the chain from the bottom up, rebuilding every power from 1 each time, and it needs an explicit accumulator and loop guard. The recursive version says the same thing more directly and mirrors the definition itself — half of a power of two is a power of two — which is exactly what the visualizer teaches.

The key insight: shrink toward the base case#

Instead of building powers up, tear n down. Ask one question about the number in front of you and hand a smaller number to a copy of yourself:

• Is it 1? Then yes — you've reached 2^0. Stop.
• Is it less than 1, or odd? Then no — a power of two above 1 is always even, so an odd value means the chain is broken. Stop.
• Otherwise it's even: divide by 2 and ask the same question about n / 2.

Each recursive call gets a strictly smaller input, so the recursion is guaranteed to terminate — either at 1 (true) or at an odd number / value below 1 (false). That's the recursion contract: a base case that stops, and a recursive step that provably moves toward it.

The optimal solution#

Three lines of logic, and the order matters:

1. n === 1 is checked first — it's the success base case, the floor of every valid chain.
2. n < 1 || n % 2 !== 0 is the failure base case. It catches zero, negatives, and any odd number greater than 1. Because line 1 already handled n === 1, this line only fires on genuine "not a power of two" values.
3. return isPowerOfTwo(n / 2) is the recursive step. There's no work left to do on the way back up — each frame just relays its child's answer unchanged. This is a straight linear recursion, not a branching one.

Walkthrough#

Trace isPowerOfTwo(16). Each row is one call frame. The recursion descends by halving, hits the base case at n === 1, then unwinds — every frame passing the same true straight back up.

The division chain 16 → 8 → 4 → 2 → 1 is the whole story. Four halvings, one base-case hit, and four relays back up. Contrast isPowerOfTwo(12): it goes 12 → 6 → 3, and at n = 3 the second check fires (3 % 2 !== 0), so that frame returns false and every frame above relays false — the chain never reaches 1.

Complexity#

The recursion reveals the halving structure at the cost of O(log n) stack space. If you only need the answer and not the intuition, the bit trick n > 0 && (n & (n - 1)) === 0 returns the same result in O(1) time and O(1) space — it works because a power of two has exactly one 1 bit in binary (16 is 10000), and subtracting 1 flips every bit below it, so the AND is zero.

Common mistakes#

• Forgetting the n < 1 guard. Without it, isPowerOfTwo(0) divides forever (0 is even, 0 / 2 is still 0) and isPowerOfTwo(-8) recurses into negatives — both are infinite loops or wrong answers. Zero and negatives must fail immediately.
• Checking n === 1 after the even/odd test. If you test n % 2 !== 0 first, n = 1 is odd and gets wrongly rejected as false. The success base case has to come first.
• Using integer division that rounds. In JavaScript n / 2 is exact for the even values you recurse on, but in languages with integer division, always confirm you only divide even numbers so no remainder is silently dropped.
• Expecting work on the way back up. Every frame here just returns its child's value unchanged. If you find yourself combining results during the unwind, you've overcomplicated a linear recursion into a branching one.

Where this pattern shows up next#

The "shrink the input toward a base case" skeleton is the foundation of every recursive algorithm:

• Sum of First N Numbers — the same descend-then-unwind shape, but each frame adds on the way back up instead of relaying.
• Sum of All Numbers in Array — recursion over an array by peeling off one element at a time.
• Factorial of N — the canonical "multiply on the way up" recursion, one step more involved than this relay.
• Recursion Masterclass — the full tour of base cases, recursive steps, and the call stack.

You can also step through Power of Two interactively to watch the call stack grow with each halving and unwind once the base case returns.

FAQ#

Why is 1 a power of two?#

Because 2^0 = 1. The exponent doesn't have to be positive — any non-negative integer counts, and 2^0 is 1 by the definition of exponents. That's why n === 1 is the success base case in the recursion: every valid halving chain bottoms out at 1, and reaching it confirms the original number was a power of two.

What is the time complexity of the recursive solution?#

O(log n) time and O(log n) space. Each recursive call halves n, so the depth of the recursion is log₂(n) — checking 16 makes 4 calls, 256 makes 8, and a million-ish value makes about 20. The stack holds one frame per level until the base case unwinds, which is where the O(log n) space comes from.

Is the bit-manipulation trick better than recursion?#

For raw performance, yes — n > 0 && (n & (n - 1)) === 0 answers in O(1) time and O(1) space, with no recursion at all. It works because a power of two has exactly one set bit, and subtracting 1 clears that bit while setting all lower ones, making the AND zero. The recursive version is slower but teaches the halving structure explicitly, which is the point when you're learning recursion.

How does the recursion handle a number that isn't a power of two?#

It halves until it hits an odd number greater than 1 (or a value below 1), and the failure base case n < 1 || n % 2 !== 0 returns false. For n = 12, the chain is 12 → 6 → 3, and 3 is odd, so that frame returns false. Every frame above it relays that false straight up without doing extra work — the answer propagates back exactly like a true would.