Power of Three: Only Exact Division Counts

A power of three survives only exact divisions by 3

To decide whether 45 is a power of three, follow a chain of divisions by 3, but create the next recursive call only when the current value divides exactly. Start with 45. Since 45 % 3 is 0, the next value is 15. Then 15 % 3 is 0, so the next value is 5. At 5, the remainder is 2, so the chain stops and the answer is false.

45 -> 15 -> 5 -> false

The decision rule has two possible endings. Reaching exactly 1 means every division succeeded, so the answer is true. Reaching a value that is not divisible by 3 means the answer is false. Dividing 5 by 3 with integer division would produce 1, but that result hides the remainder and does not prove that 5 came from an exact division.

The remainder check must happen before the recursive call

The function checks the successful base case first, then rejects values that cannot continue exactly. Only after those checks does it call itself with n / 3. For 45, the calls use 15 and then 5. At 5, the rejection condition runs before integer division, so the function returns false instead of calling itself with 5 / 3.

bool isPowerOfThree(int n) {
    if (n == 1) {
        return true;
    }
    if (n <= 0 || n % 3 != 0) {
        return false;
    }
    return isPowerOfThree(n / 3);
}

At 5, the expression 5 / 3 has the integer value 1 in C++. If the function calls itself with that value, it reaches the successful base case and returns true. That is a false positive: 5 is not a power of three. The remainder check must therefore come before n / 3, not after it.

Every recursive call preserves the original question

The call on 45 asks whether 45 is a power of three. Because 45 is exactly 3 times 15, 45 is a power of three if and only if 15 is a power of three. The same reasoning changes the question from 15 to 5, because 15 is exactly 3 times 5. At 5, the remainder check rejects the value, so the call on 5 returns false.

isPowerOfThree(45)
  -> isPowerOfThree(15)
       -> isPowerOfThree(5)
            -> false
       <- false
  <- false

The result then travels back without changing. The call for 5 returns false to the call for 15, and the call for 15 returns false to the call for 45. No call needs to inspect a different rule on the way back, because each earlier value was accepted only as an exact multiple of the value below it.

if (n == 1) return true;
// add the rejection condition here
return isPowerOfThree(n / 3);

Dividing by 3 makes the call chain logarithmic

The trace for 45 contains three calls: one for 45, one for 15, and one for 5. The concrete costs are T(45) = T(15) + O(1), T(15) = T(5) + O(1), and T(5) = O(1), because the call at 5 stops at the remainder check.

T(45) = T(15) + O(1)
T(15) = T(5) + O(1)
T(5) = O(1)

T(n) = T(n / 3) + O(1)

Each recursive call divides the current value by 3, so the number of calls grows logarithmically with the starting value. The worst-case time is O(log n). The calls remain active while the deeper call runs, so the call stack also holds O(log n) frames in the worst case. For 45, both bounds are visible as a chain of three calls.