DSA sheet · Recursion · Linear recursion pattern

Pow(x, n)

This is the last question of the linear recursion pattern. We must compute x raised to the power n, where n can be negative and can be as big as about two billion. The teacher first shows the obvious way (multiply x again and again, n times), then shows the trick that makes it fast: to get x¹⁰, get x⁵ once and multiply it by itself. That halving idea turns O(n) into O(log n). She writes it first as a while loop and then converts the loop into a recursive function.

Why it matters: this is the classic example that recursion does not always mean "slow" or "2ⁿ". A recursion that makes one call per step and halves its input each time has only log n levels.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run (recursion tree + call stack) → ⑨ complexity & remember

• Part 0 · Recursion from scratch (what you need for this page)
• Part A · Brute force: multiply n times (loop and naive recursion)
• Part B · Fast power by halving (recursion that builds the answer on the way up)
• Part C · The same idea as a while loop (the teacher's first code)
• Part D · The loop turned into parameterized recursion (the teacher's second code)
• Part E · Revision page

Part 0 · Recursion from scratch

1. A function that calls itself

Recursion means a function solves a problem by calling itself on a smaller version of the same problem. For powers this is very natural:

• 2⁵ is just 2 × 2⁴. And 2⁴ is 2 × 2³. And so on.
• So "power(2, 5)" can say: "I will ask power(2, 4) for its answer, and then multiply by one more 2."

2. The base case: where it must stop

The base case is the smallest input whose answer we know directly, without another call. For powers it is n = 0: anything to the power 0 is 1.

3. The recursive case: make the problem smaller

The recursive case is the line that calls the function again with a smaller input, and then uses that answer. Every call must move closer to the base case (here: n must shrink towards 0), otherwise we never reach it.

4. Trust the smaller call ("leap of faith")

When you write half = power(x, n // 2), don't try to trace the whole chain in your head. Just assume it correctly returns x^n//2, and ask only: "Given that answer, how do I build xⁿ?" If the base case is right and each step is right, the whole thing is right. This trust is called the leap of faith.

5. The call stack: push on call, pop on return

Python keeps a call stack: a pile of the calls that have started but not finished.

• When a function calls another, the new call is pushed on top. The caller pauses and waits.
• When a call returns, it is popped off the top, and its answer goes to the call just below it, which then continues.

The number of calls stacked up at the deepest moment is the depth of the recursion. That depth is the extra memory (space) the recursion uses.

6. Work on the way down vs work on the way back up

The teacher refers to two styles from her earlier video. You will see both on this page:

7. Two facts about powers we need

• Negative power = flip the base. 2⁻¹ = 1/2 = 0.5, and 2⁻² = (1/2)² = 0.25. So x⁻ⁿ = (1/x)ⁿ: replace x by 1/x and make n positive.
• Halving the power: x¹⁰ = x⁵ × x⁵. And for an odd power, x⁵ = x² × x² × x (one x is left over).

Part A · Brute force: multiply x, n times

LeetCode 50 · Pow(x, n)

1The question in simple words

Given a decimal number x and a whole number n, return xⁿ as a decimal number (a float in Python).

Because x is a decimal, the answer must also be a decimal. The teacher keeps the answer in a double variable. In Python we start with 1.0, so everything stays a float.

2What the constraints tell us

• −100.0 < x < 100.0: x can be negative too. That needs no special handling: (−2)³ = −8 comes out right just by multiplying.
• −2³¹ ≤ n ≤ 2³¹ − 1: n can be negative, so we must handle the flip. And n can be about 2 × 10⁹, which is far above the ~10⁸ operations that pass in time. An O(n) solution will TLE (Time Limit Exceeded). We need something faster.
• Either x ≠ 0 or n > 0: we never get 0 to a negative power, so 1 / x never divides by zero.
• −10⁴ ≤ xⁿ ≤ 10⁴: the final answer is a normal-sized number.

3Intuition

The first idea anyone has: power means "multiply x by itself n times". So start with 1 and multiply by x, n times. If n is negative, first flip x to 1/x and make n positive, then do the same.

4Building the logic from the examples

• Example 1 (x = 2, n = 10): n is positive, so nothing to flip. Multiply 1 by 2 ten times → 1024.
• Example 3 (x = 2, n = −2): the minus sign only means "move the base to the bottom". So two changes: x becomes 1/2 = 0.5, and n becomes +2. Then 0.5 × 0.5 = 0.25 ✓.

The same as a recursion: xⁿ = x × xⁿ⁻¹, with base case x⁰ = 1. Each call does one multiplication and passes "n − 1" down.

5Approach steps

1. If n < 0: set x = 1/x and n = −n.
2. Start ans = 1.0.
3. Repeat n times: ans = ans * x.
4. Return ans. (Recursive form: power(x, n) = x × power(x, n − 1), and power(x, 0) = 1.)

6Code (Python)

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:                 # negative power: flip the base
            x = 1 / x
            n = -n
        ans = 1.0
        for _ in range(n):        # multiply n times
            ans = ans * x
        return ans

def power_naive(x, n):            # assumes n >= 0
    if n == 0:                    # base case: x^0 = 1
        return 1.0
    return x * power_naive(x, n - 1)   # x^n = x * x^(n-1)

7Code line by line

8Dry run: the naive recursion for 2¹⁰

Each line of the tree is one call: p(n) → returned value. Every call makes exactly one smaller call, so the "tree" is a straight line.

p(10) → 1024
  |
p(9)  → 512
  |
p(8)  → 256
  |
p(7)  → 128
  |
 ...      (one call for every n)
  |
p(1)  → 2
  |
p(0)  → 1     ← base case
                 11 calls, 11 levels deep

1. p(10) needs p(9), so it pauses. p(9) needs p(8), and so on. Each one is pushed on the stack.
2. p(0) hits the base case and returns 1. It is popped.
3. p(1) receives 1 and returns 2 × 1 = 2. Popped.
4. p(2) returns 2 × 2 = 4, p(3) returns 8, … each return does one multiplication on the way up.
5. p(10) receives 512 and returns 2 × 512 = 1024 ✓.

9Complexity & remember

• Time O(n): n multiplications (n + 1 calls in the recursive form).
• Space: O(1) for the loop; O(n) for the recursion, because all n calls wait on the stack at once.
• With n up to 2³¹ ≈ 2.1 × 10⁹, the loop is way over the time limit. The recursion is even worse in Python: it crashes after about 1000 levels. sys.setrecursionlimit can raise that number, but two billion stack frames will never fit in memory.

Part B · Fast power by halving (recursive)

1The question

The same question: return xⁿ. But now we want it in far fewer than n steps.

2What the constraints tell us

n up to ~2 × 10⁹ means we need roughly O(log n): log₂(2³¹) is just 31. That's a huge hint to "cut the problem in half at each step".

3Intuition: the teacher's "left half, right half" picture

When we multiply 2 ten times, we're repeating work. Split the ten 2's into two equal groups:

2¹⁰ = (2 × 2 × 2 × 2 × 2) × (2 × 2 × 2 × 2 × 2)
       └──── left half ────┘   └──── right half ───┘
              = 2⁵                     = 2⁵  (the SAME number!)

If we somehow get the left half, 2⁵ = 32, we don't need to compute the right half at all: it's the same 32. One multiplication, 32 × 32, gives 1024. We just saved all the work of the right half.

Now apply the same trick to 2⁵, then to whatever that needs, until the power is 0.

4Building the logic from the example 2¹⁰

The teacher breaks it down step by step:

• 2¹⁰: "give me 2⁵ and I'll multiply it by itself."
• 2⁵: 5 is odd, so it doesn't split into two equal halves. 5 = 2 + 2 + 1. "Give me 2², I'll multiply it by itself to get 2⁴, then multiply by one extra 2 for the leftover."
• 2²: "give me 2¹ and I'll multiply it by itself."
• 2¹: 1 is odd. 1 = 0 + 0 + 1. "Give me 2⁰, square it, multiply by one extra 2."
• 2⁰: the power is 0. Stop. Whatever the base is, the answer is 1. This is the base case.

Now the answers travel back up:

• 2¹ = 1 × 1 × 2 = 2
• 2² = 2 × 2 = 4
• 2⁵ = 4 × 4 = 16, odd so × 2 → 32
• 2¹⁰ = 32 × 32 = 1024 ✓

That's just 4 halving steps instead of 10 multiplications in a row.

5Approach steps

1. If n < 0: x = 1/x, n = −n.
2. power(x, n): if n == 0 return 1.
3. half = power(x, n // 2), computed once.
4. If n is even return half × half; if odd return half × half × x.

6Code (Python)

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:                       # negative power: flip the base
            x = 1 / x
            n = -n                      # Python ints never overflow, even for -2**31
        return self.power(x, n)

    def power(self, x, n):
        if n == 0:                      # base case: x^0 = 1
            return 1.0
        half = self.power(x, n // 2)    # ONE call, for half the power
        if n % 2 == 1:                  # odd: one x is left over
            return half * half * x
        return half * half              # even: two equal halves

7Code line by line

8Dry run: why the call tree has only log n levels

Put the two recursion trees for 2¹⁰ side by side. Each node shows call → returned value.

p(10) → 1024
p(9)  → 512
p(8)  → 256
p(7)  → 128
p(6)  → 64
p(5)  → 32
p(4)  → 16
p(3)  → 8
p(2)  → 4
p(1)  → 2
p(0)  → 1
11 levels

power(2,10) → 1024   = 32·32
     |
power(2,5)  → 32     = 4·4·2
     |
power(2,2)  → 4      = 2·2
     |
power(2,1)  → 2      = 1·1·2
     |
power(2,0)  → 1      base case

5 levels

1. power(2,10) pauses and calls power(2,5). stack: [10]
2. power(2,5) pauses and calls power(2,2). stack: [10, 5]
3. power(2,2) calls power(2,1). power(2,1) calls power(2,0). stack: [10, 5, 2, 1, 0]: the deepest moment, 5 calls.
4. power(2,0) returns 1 and is popped.
5. power(2,1): half = 1, n is odd → 1 × 1 × 2 = 2. Popped.
6. power(2,2): half = 2, even → 2 × 2 = 4. Popped.
7. power(2,5): half = 4, odd → 4 × 4 × 2 = 32. Popped.
8. power(2,10): half = 32, even → 32 × 32 = 1024 ✓. The stack is empty.

Counting the levels. The naive version subtracts 1, so it needs n + 1 calls to get from n down to 0. The halving version divides by 2, so after k calls the power is about n / 2^k. It reaches 0 once 2^k > n, i.e. after about log₂ n + 2 calls.

Both are linear recursion (one call per call, so the tree is a single chain). The difference is only how fast the input shrinks: −1 per level gives n levels, ÷2 per level gives log n levels. 33 levels is far below Python's limit of ~1000, so no setrecursionlimit is needed.

9Complexity & remember

• Time O(log n): about log₂ n calls, each doing 1–2 multiplications.
• Space O(log n): the stack is as deep as the chain, about log₂ n frames.

Part C · The halving idea as a while loop (teacher's first code)

The teacher first writes the fast idea without recursion, then converts it. The loop goes in the opposite direction from Part B: instead of breaking 2¹⁰ down and building back up, it walks the power down and keeps squaring the base as it goes.

1–2Question & constraints

The same as Part A. The negative-n flip is done the same way at the start.

3Intuition

Keep three things: the answer so far (ans, starts at 1), the current base x, and the power still left (exp). At each step:

• If exp is odd, one copy of the current base is "left over" → multiply it into ans.
• Square the base (x → x·x) and halve the power (exp → exp // 2). This keeps "the value still owed" the same: x^exp = (x·x)^exp/2.

Stop when exp reaches 0. Then ans holds the full answer.

4Building the logic: why "odd → multiply into ans"

Look at 10 in binary: 1010 = 8 + 2. So 2¹⁰ = 2⁸ × 2². The loop visits the bases 2¹, 2², 2⁴, 2⁸ (squaring each time). The steps where exp is odd are exactly the 1-bits of 10, so ans picks up 2² and 2⁸ and skips 2¹ and 2⁴. 4 × 256 = 1024 ✓. That's why the check is "is exp odd?".

5Approach steps

1. exp = n. If exp < 0: x = 1/x, exp = −exp.
2. ans = 1.0.
3. While exp > 0: if exp is odd, ans *= x. Then x = x·x and exp = exp // 2.
4. Return ans.

6Code (Python)

class Solution:
    def myPow(self, x: float, n: int) -> float:
        exp = n                      # (Java/C++ need a long here)
        if exp < 0:
            x = 1 / x
            exp = -exp
        ans = 1.0
        while exp > 0:
            if exp % 2 == 1:         # odd: take one copy of x into the answer
                ans = ans * x
            x = x * x                # square the base
            exp = exp // 2           # halve the power
        return ans

7Code line by line

8Dry run: the teacher's table for x = 2, n = 10

There's no recursion here, so there's no call stack. The next part turns this exact loop into recursion.

9Complexity & remember

• Time O(log n): exp halves every round, so there are ⌊log₂ n⌋ + 1 rounds. On LeetCode it ran as fast as possible.
• Space O(1): just three variables.

Part D · The loop turned into parameterized recursion (teacher's second code)

Now the teacher converts the while loop into a recursive function. The rule she follows: everything that changes in the loop becomes a parameter, and the loop's stop condition becomes the base case.

1–3Question, constraints, intuition

The same question, and the same flip for negative n. The loop changed three things each round: x, exp and ans. So the function takes all three: power(x, n, ans). The first call is power(x, exp, 1.0), because ans started at 1.

4Building it from the loop

5Approach steps

1. Flip for negative n, then return power(x, exp, 1.0).
2. power: if n == 0 → return ans.
3. If n is odd → ans = ans × x.
4. Return power(x × x, n // 2, ans).

6Code (Python)

class Solution:
    def myPow(self, x: float, n: int) -> float:
        exp = n
        if exp < 0:
            x = 1 / x
            exp = -exp
        return self.power(x, exp, 1.0)

    def power(self, x, n, ans):
        if n == 0:                   # the loop's stop condition
            return ans               # answer is already complete
        if n % 2 == 1:               # odd: take one x into the answer
            ans = ans * x
        return self.power(x * x, n // 2, ans)   # square base, halve power

7Code line by line

8Dry run: x = 2, n = 10

Recursion tree (a single chain). Each node shows its arguments and what it returns:

power(x=2,     n=10, ans=1)     → 1024
   |  10 even: ans stays 1
power(x=4,     n=5,  ans=1)     → 1024
   |  5 odd: ans = 1·4 = 4
power(x=16,    n=2,  ans=4)     → 1024
   |  2 even: ans stays 4
power(x=256,   n=1,  ans=4)     → 1024
   |  1 odd: ans = 4·256 = 1024
power(x=65536, n=0,  ans=1024)  → 1024   ← base case

1. Going down. Each call does its small piece of work (maybe multiply into ans), then calls the next one with the squared base and the halved power. Compare with Part C: the arguments are exactly the loop's table, one row per call.
2. The 5th call has n = 0 → it returns 1024.
3. Coming back up. Each call just passes the same 1024 to the one below it. No calculation happens on the way up.
4. myPow returns 1024 ✓.

9Complexity & remember

• Time O(log n): ⌊log₂ n⌋ + 2 calls (5 for n = 10, 33 for n = 2³¹). It submitted with the same speed as the loop.
• Space O(log n): the stack holds that many frames. (Python doesn't remove frames for "tail calls", so even though nothing happens on the way up, the frames still wait.)
• The teacher's point about the pattern: this is linear recursion (one call per call), but the time is logarithmic, not linear, because we skip the other half every time. She kept it in the linear pattern so she didn't need a separate pattern just for it. The lesson: recursion is not always 2ⁿ. It can be linear or even logarithmic.

Part E · Revision page

s = Solution()
print(s.myPow(2.0, 10))         # 1024.0
print(s.myPow(2.1, 3))          # 9.261 (approximately)
print(s.myPow(2.0, -2))         # 0.25
print(s.myPow(5.0, 0))          # 1.0
print(s.myPow(-2.0, 3))         # -8.0
print(s.myPow(1.0, -2**31))     # 1.0  (smallest n, fast)
print(s.myPow(2.0, -2**31))     # 0.0  (far too small for a float)

Based on this video: Pow(x, n) | Linear Recursion