My power function crashes when n is 5,000

New to some of the words above? Open a quick recap. Each takes about two minutes.

Quick recapFunctions in two minutes· 2 min

def makes a function. Each call gets its own names, so two calls of the same function don’t share an n. return hands back the answer and ends that call at once. A function can call another one, and it waits for that answer before it goes on.

def double(n):
    return 2 * n

def quad(n):
    return double(double(n))   # waits for each double() to answer

quad(3)    # 12

Quick recapBig-O in two minutes· 2 min

Big-O says how the work grows as the input grows. One loop over n items is O(n): twice the items, twice the work. O(log n) means each step halves what’s left, so a million items take about 20 steps. Space is the same idea for the extra memory. The full lesson: My code passed every test, then timed out on the big one.

See the problem

The interview task: work out x to the power n, without **. You think: x to the n is x times x to the n − 1, so the function can call itself.

def power(x, n):
    if n == 0:
        return 1.0
    return x * power(x, n - 1)

power(2.0, 10) gives 1024.0. Then the interviewer tries power(1.0001, 5000):

RecursionError: maximum recursion depth exceeded

The maths is fine. But each call of power waits for the call it made, and Python lets only about 1,000 calls wait at once. n = 5,000 needs 5,001.

Define the task

Write power(x, n).

• Input: a float x, and a whole number n from −1,000,000,000 to 1,000,000,000. When n is below 0, x isn’t 0.
• Output: x to the power n, as a float. A power below 0 means 1 divided: power(2.0, -2) is 1 / 4 = 0.25.
• The hard part: build it from calls to power, without ** or pow(). It must work for n = 5,000, and be fast for n = 1,000,000,000.

Example: power(2.0, 10) gives 1024.0. power(5.0, 0) gives 1.0.

Pause and think

⏸ Pause and think

Before you write any code: x⁸ is x⁴ × x⁴. If you keep halving like that, how many steps does x to the power 1,000,000,000 take?

Give it two minutes with pen and paper before you open a hint.

Hints open one at a time:

Hint 1 of 3

x⁸ = x⁴ × x⁴, and x⁴ = x² × x². Each step halves the power, so a billion takes about 30 steps.

Hint 2 of 3

An odd power has one x left over: x⁷ = x³ × x³ × x.

Hint 3 of 3

Work out x to the n // 2 once, keep it in a variable, and multiply it by itself.

Understand the idea

Recursion is a function that calls itself on a smaller piece. It needs two parts:

• A base case: an input small enough to answer at once. For power, n = 0 gives 1.0.
• A step that makes the input smaller and calls itself: power(x, n - 1), then times x. Every input must reach the base case.

Trust the smaller call. You don’t have to follow every call in your head. Check the base case is right. Then assume power(x, n - 1) is right, and check your line turns it into the right answer for n. If both hold, every n works, one step at a time.

Each call waits for the one it made. power(2, 3) can’t multiply until power(2, 2) answers, and that one waits for power(2, 1). Python keeps every call in progress, each with its own n, on the call stack. When the base case returns, the answers come back up, one call at a time.

Python allows about 1,000 calls in progress. Each one holds memory, so Python stops a chain that gets too deep with RecursionError. It’s not the number of calls in all that counts: a program can make millions, as long as few are in progress at once.

Watch it. Each box is one call, under the call that made it. The panel counts the calls made, and how many are in progress. Try your own n, from −7 to 7.

Call it with n − 1

⤢ Full view

Calls so far, each under the call that made it:

• power(2, 5): running now

Work so far

calls made	1
in progress now	1
most in progress at once	1

• Running now
• Waiting for a call it made
• Done: shows what it returned

Step 1 of 12. power(2, 5) needs power(2, 4) first. It calls it, and waits for the answer. Question: With n = 5, how many calls will be in progress at once, at most?

What happens next? With n = 5, how many calls will be in progress at once, at most?

156Just show me

◀ BackPlayNext ▶Reset Ask me first Show as text

1def power(x: float, n: int) -> float:
2    if n < 0:
3        return 1 / power(x, -n)
4    if n == 0:
5        return 1.0
6    return x * power(x, n - 1)

Try your own input

n, for power(2, n)Show it

Count the work by drawing the tree. The number of boxes is the number of calls: with O(1) work in each, that’s the time. The longest line from the top down is the most calls in progress at once: the memory, and what RecursionError counts. For Okay, the tree is one line of n + 1 boxes, so both are O(n).

★The boxes are the time, the height is the memory

Draw the calls as a tree, each under the call that made it. How many boxes there are is the time. How tall it is is the memory, and Python stops a tree that grows past about 1,000 tall.

Any recursion can be a loop. The call stack is just a list of calls in progress. Keep your own list, and a loop can do the same work, with no limit but memory. Practice problems 1 and 2 do that.

Climb the ladder

All three give 1024.0 for power(2.0, 10). What changes is how many calls they make, and how many are in progress at once.

Okay

Call it with n − 1

The idea: x to the n is x times x to the n − 1. Stop at n = 0, which is 1. A power below 0 is 1 divided by the power above 0.

Right, short, and it reads like the maths.

def power(x: float, n: int) -> float:
    if n < 0:
        return 1 / power(x, -n)
    if n == 0:
        return 1.0
    return x * power(x, n - 1)

Time

O(n)

Space

O(n)

Why

One call for each n, from n down to 0. All n + 1 are in progress at once when the base case runs, each holding its own n.

Where it breaks: depth. n = 5,000 needs 5,001 calls in progress, and Python stops at about 1,000: RecursionError. Even with no limit, n = 1,000,000,000 would make a billion calls.

Better

Halve n, but make the call twice

The idea: x⁶ is x³ × x³, and x⁷ is x³ × x³ × x. So power(x, n) multiplies power(x, n // 2) by itself, and by one more x when n is odd.

The waste in Okay: going down by 1 takes n calls to reach 0. Halving reaches 0 in about log₂ n, so few calls are ever in progress: 14 for n = 5,000.

Halve n, but make the call twice

⤢ Full view

Calls so far, each under the call that made it:

• power(2, 6): running now

Work so far

calls made	1
in progress now	1
most in progress at once	1

• Running now
• Waiting for a call it made
• Done: shows what it returned

Step 1 of 30. power(2, 6) needs power(2, 3) twice, once for each side of the ×. It calls the first. Question: With n = 6, how many calls will power make in all?

What happens next? With n = 6, how many calls will power make in all?

4715Just show me

◀ BackPlayNext ▶Reset Ask me first Show as text

1def power(x: float, n: int) -> float:
2    if n < 0:
3        return 1 / power(x, -n)
4    if n == 0:
5        return 1.0
6    result = power(x, n // 2) * power(x, n // 2)
7    if n % 2 == 1:
8        result *= x
9    return result

Try your own input

n, for power(2, n)Show it

Highlighted lines are new in this rung.

def power(x: float, n: int) -> float:
    if n < 0:
        return 1 / power(x, -n)
    if n == 0:
        return 1.0
    result = power(x, n // 2) * power(x, n // 2)
    if n % 2 == 1:
        result *= x
    return result

Time

O(n)

Space

O(log n)was O(n)

Why

Each call halves n, so only about log₂ n calls are in progress at once. But each call makes two calls, so every row of the tree has twice as many as the row above: about 2n calls in all.

What changed from the previous rung

def power(x: float, n: int) -> float:
    if n < 0:
        return 1 / power(x, -n)
    if n == 0:
        return 1.0
    return x * power(x, n - 1)
    result = power(x, n // 2) * power(x, n // 2)
    if n % 2 == 1:
        result *= x
    return result

Where it breaks: speed. Line 6 calls power(x, n // 2) once for each side of the *, and nothing keeps the first answer. So the tree doubles every row, and n = 1,000,000,000 makes over 2 billion calls: it runs out of time. For n = 6 it makes 15, more than Okay’s 7.

Best

Halve n, and make the call once

The idea: Work out half = power(x, n // 2) once. Return half × half, times one more x when n is odd.

The waste in Better: it asks the same question twice. Keep the first answer in a variable, and the tree becomes one short line: 31 calls for n = 1,000,000,000.

Halve n, and make the call once

⤢ Full view

Calls so far, each under the call that made it:

• power(2, 6): running now

Work so far

calls made	1
in progress now	1
most in progress at once	1

• Running now
• Waiting for a call it made
• Done: shows what it returned

Step 1 of 8. power(2, 6) works out power(2, 3) once, as half. Question: With n = 6, how many calls will power make in all?

What happens next? With n = 6, how many calls will power make in all?

4715Just show me

◀ BackPlayNext ▶Reset Ask me first Show as text

1def power(x: float, n: int) -> float:
2    if n < 0:
3        return 1 / power(x, -n)
4    if n == 0:
5        return 1.0
6    half = power(x, n // 2)  # once, not twice
7    result = half * half
8    if n % 2 == 1:
9        result *= x
10    return result

Try your own input

n, for power(2, n)Show it

Highlighted lines are new in this rung.

def power(x: float, n: int) -> float:
    if n < 0:
        return 1 / power(x, -n)
    if n == 0:
        return 1.0
    half = power(x, n // 2)  # once, not twice
    result = half * half
    if n % 2 == 1:
        result *= x
    return result

Time

O(log n)was O(n)

Space

O(log n)

Why

One call for each halving of n, down to 0: about log₂ n + 2 calls, and they are all in progress at once at the bottom.

What changed from the previous rung

def power(x: float, n: int) -> float:
    if n < 0:
        return 1 / power(x, -n)
    if n == 0:
        return 1.0
    result = power(x, n // 2) * power(x, n // 2)
    half = power(x, n // 2)  # once, not twice
    result = half * half
    if n % 2 == 1:
        result *= x
    return result

When Best isn’t best: in real code, write x ** n, or pow(x, n, m) for the remainder after dividing by m: both run in C. And floats run out. 2.0 ** 2000 raises OverflowError, where half * half quietly gives inf.

Write it yourself

Now write it in the page. Press Run tests to check your code. Python runs in your browser, so nothing is sent anywhere. Your code is saved in this browser for next time.

Try Okay from the ladder first: it fails the n = 5,000 and speed tests with RecursionError. Better runs out of time on the speed test.

Work out x to the power n

Ctrl + Enter runs

def power(x: float, n: int) -> float: # x to the power n. n is a whole number, and can be below 0. # Build it from calls to power, without ** or pow(). return 1.0

Run testsReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: power(2.0, 10)
2. ○Not run yet: power(2.0, -2)
3. ○Not run yet: power(5.0, 0)
4. ○Not run yet: Extra test
5. ○Not run yet: Extra test
6. ○Not run yet: n = 5,000: power(1.0001, 5000), rounded to 5 places
7. ○Not run yet: Speed test: power(1.000000001, 1,000,000,000), rounded to 5 places

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

power()Run onceVisualize

Compare

Way	Time	Extra memory	Good	Not so good	Use it when
Okay: call it with n − 1	O(n)	O(n): n calls in progress	The simplest recursion	RecursionError past about 1,000	n stays small, or to explain recursion
Better: halve n, call twice	O(n)	O(log n)	Few calls in progress, so no crash	About 2n calls, more than Okay	Never: it’s Best with one slip
Best: halve n, call once	O(log n)	O(log n)	31 calls for a billion	A few more lines than Okay	Always, or x ** n in real code

How much work is that? Each bar is one rung, for x to the power n. Pick a size, or run the race.

power(x, n): calls for n

1. OkayCall it with n − 1 · O(n)≈ 1,000,000 calls

2. BetterHalve n, call twice · O(n)≈ 2,100,000 calls

3. BestHalve n, call once · O(log n)≈ 21 calls

At n = 1,000,000, Better does about 100,000 times more work than Best.

Every bar does the same number of steps per second, so the race shows which rung finishes first. Turn on Log scale to compare the short bars.

The race counts calls, and here every call does about the same work. But Okay never gets past about 1,000: Python stops it with RecursionError long before the race does.

Common mistakes and edge cases

!A step that doesn’t get smaller never stops

If a call can reach itself with the same input, or step past the base case, it calls until RecursionError. A step of power(x, n - 2) from an odd n goes 3, 1, −1, −3, … and never hits 0. Check that every input reaches the base case.

• Python doesn’t turn a last call into a loop. Some languages reuse the call when it’s the last thing a function does. Python never does, so return helper(n - 1) still adds a call in progress.
• sys.setrecursionlimit() can crash Python. It lets the chain go deeper, but the real stack underneath can still run out, and then Python dies instead of raising an error. For deep work, use a loop.
• f(nums[1:]) copies the list every call. That’s O(n²) for a list of n. Pass an index instead: f(nums, i + 1).
• A mutable default is shared by every call. def f(n, seen=[]) makes one list, when def runs, and every call that doesn’t pass seen adds to it. Use seen=None, make a new list when it’s None, and pass it down.
• 0 to a power below 0 is an error. power(0.0, -3) divides by 0 and raises ZeroDivisionError, as 0.0 ** -3 does.
• Floats run out. 2.0 ** 2000 raises OverflowError, but half * half gives inf without a word. A whole number x with x ** n gives an exact whole number of any size.

Say it in the interview

Questions to ask first

• Can n be below 0? Can x be 0 then?
• Floats, or whole numbers with a remainder, like pow(x, n, m)?
• How big can n get?

A 60-second walkthrough

“x to the n is x to the n // 2, squared, times one more x if n is odd. So each call halves n, and the base case is n = 0, which gives 1. For a negative n, I return 1 over power(x, −n). The key is to work out the half once and keep it in a variable: calling it twice would double the calls on every row, and make about 2n of them. With one call, it’s about log₂ n calls, so O(log n) time. And O(log n) calls are in progress at once, about 31 for n up to two billion. That’s far under Python’s limit of about 1,000. In real code I’d write x ** n.”

Likely follow-ups

• Can you do it without recursion? Yes. Loop over n’s bits: square x each time, and multiply it into the answer when the bit is 1. O(log n) time and O(1) memory.
• With a remainder, pow(x, n, m)? The same halving. Take % m after each multiply, so the numbers stay small.
• Why not save Better’s answers with @functools.cache? That fixes it too, but here each half is needed only right away, so a variable is enough. Saving answers to use later is the start of dynamic programming.
• What’s the recursion limit? About 1,000 by default: sys.getrecursionlimit(). You can raise it, but deep recursion is better as a loop.

Practice

Three problems, from easy to medium. Each has a recursion, a place where Python’s limit bites, and a way past it. Each has hints, tests you can run here, and its own Okay, Better and Best answers. For each rung, say its Big-O before you open it.

1. The size of a folder (easy)

Write folder_size(folder): the total size, in bytes, of every file in folder and in the folders inside it. A folder is a dict. Each name in it maps to a whole number, a file’s size, or to another dict, a folder inside.

Example: folder_size({'notes.txt': 120, 'photos': {'a.jpg': 3000, 'b.jpg': 2500}}) gives 5620.

Hint 1 of 3

A file is just its size. A folder is the sum of what’s inside it, and a folder inside is a smaller copy of the same problem.

Hint 2 of 3

Loop over folder.values(). For each dict, call folder_size on it. For each number, add it.

Hint 3 of 3

Python stops at about 1,000 calls in progress. To go deeper, keep a list of folders still to open, and loop until it’s empty.

The size of a folder

Ctrl + Enter runs

def folder_size(folder: dict) -> int: # The total size of every file in folder, # and in the folders inside it. return 0

Run testsVisualizeReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: folder_size({'notes.txt': 120, 'photos': {'a.jpg': 3000, 'b.jpg': 2500}}) → 5620
2. ○Not run yet: folder_size({}) → 0
3. ○Not run yet: Folders inside folders, and no files → 0
4. ○Not run yet: Extra test
5. ○Not run yet: One folder of 5,000 files → 12497500
6. ○Not run yet: Folders 1,200 deep, with a 1-byte file in each → 1200

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

folder_size()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Add the first item, then call again on the rest

The idea: Make a list of what’s in the folder. Its size is the first item’s size, plus the size of the rest, worked out by calling again.

It’s the shape many people meet first: the first item, then the rest.

def folder_size(folder: dict) -> int:
    """The total size of every file in folder, and in the folders inside it."""
    return add_up(list(folder.values()))


def add_up(items: list) -> int:
    if not items:
        return 0
    first = items[0]
    size = folder_size(first) if isinstance(first, dict) else first
    return size + add_up(items[1:])  # a copy of the rest, one call deeper

Time

O(n²)

Space

O(n²)

Why

For a folder of n items, each call copies the rest of the list: n − 1, then n − 2, and so on. Every copy is kept until its call ends.

Where it breaks: a call for every file. One folder of 5,000 files needs 5,000 calls in progress: RecursionError.

Better

Loop over the items, and call only for folders

The idea: Add up the files with a loop. For each folder inside, call folder_size on it and add what it returns.

The waste in Okay: it made a call, and a copy, for every file. Only a folder has more inside, so only a folder needs a call.

Highlighted lines are new in this rung.

def folder_size(folder: dict) -> int:
    """The total size of every file in folder, and in the folders inside it."""
    total = 0
    for item in folder.values():
        if isinstance(item, dict):
            total += folder_size(item)  # one call for each folder inside
        else:
            total += item
    return total

Time

O(n)was O(n²)

Space

O(d)was O(n²)

Why

Each of the n files and folders is looked at once. Only the folders on the way down to the one being read are in progress: d of them, d being how deep the folders go.

What changed from the previous rung

def folder_size(folder: dict) -> int:
    """The total size of every file in folder, and in the folders inside it."""
    return add_up(list(folder.values()))


def add_up(items: list) -> int:
    if not items:
        return 0
    first = items[0]
    size = folder_size(first) if isinstance(first, dict) else first
    return size + add_up(items[1:])  # a copy of the rest, one call deeper
    total = 0
    for item in folder.values():
        if isinstance(item, dict):
            total += folder_size(item)  # one call for each folder inside
        else:
            total += item
    return total

Where it breaks: folders 1,200 deep still need 1,200 calls in progress: RecursionError. Real folders are rarely that deep, so this is often fine.

Best

Keep your own stack of folders to open

The idea: Start a list with the folder. Take one off, add up its files, and put its folders on the list. Stop when the list is empty.

The waste in Better: none in work. But Python’s call stack is small, and a list can grow as far as memory allows. Taking a folder off the list is what a call starting did.

Highlighted lines are new in this rung.

def folder_size(folder: dict) -> int:
    """The total size of every file in folder, and in the folders inside it."""
    total = 0
    to_open = [folder]  # folders not read yet: our own stack
    while to_open:
        for item in to_open.pop().values():
            if isinstance(item, dict):
                to_open.append(item)
            else:
                total += item
    return total

Time

O(n)

Space

O(f)was O(d)

Why

Each file and folder is handled once. The list holds the folders found but not opened yet: at most all f of them.

What changed from the previous rung

def folder_size(folder: dict) -> int:
    """The total size of every file in folder, and in the folders inside it."""
    total = 0
    for item in folder.values():
        if isinstance(item, dict):
            total += folder_size(item)  # one call for each folder inside
        else:
            total += item
    to_open = [folder]  # folders not read yet: our own stack
    while to_open:
        for item in to_open.pop().values():
            if isinstance(item, dict):
                to_open.append(item)
            else:
                total += item
    return total

When Best isn’t best: for real folders, Better is shorter and easier to read. And for files on disk, os.walk() and Path.rglob('*') already walk the folders for you, without recursion.

2. Decode a string (medium)

Write decode(s). In s, k[text] means text repeated k times, and brackets can be inside brackets. k is a whole number from 1 up, and s has only lowercase letters, digits and brackets that always match.

Example: decode('3[a]2[bc]') gives 'aaabcbc'. decode('3[a2[c]]') gives 'accaccacc': 2[c] is cc, so a2[c] is acc, three times.

Hint 1 of 3

The last [ in s has no [ after it, so nothing is inside it. Expanding it and starting again works, but each pass rebuilds all of s.

Hint 2 of 3

Read s once, left to right. When you meet a [, the part up to its ] is a smaller copy of the same problem: decode it with a call, then repeat it.

Hint 3 of 3

Python stops at about 1,000 calls in progress. Instead of a call for each [, keep a list: on [, put the parts so far and the number on it. On ], take them off and join.

Decode a string

Ctrl + Enter runs

def decode(s: str) -> str: # Expand every k[text] in s into text repeated k times. return s

Run testsVisualizeReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: decode('3[a]2[bc]') → 'aaabcbc'
2. ○Not run yet: decode('3[a2[c]]') → 'accaccacc'
3. ○Not run yet: decode('2[abc]3[cd]ef') → 'abcabccdcdcdef'
4. ○Not run yet: Extra test
5. ○Not run yet: Extra test
6. ○Not run yet: Speed test: 2[ab], 100,000 times side by side
7. ○Not run yet: Brackets 3,000 deep: 1[1[ … 1[a] … ]] → 'a'

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

decode()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Expand the innermost brackets, again and again

The idea: The last [ in s has nothing inside it. Expand it, put the result back into s, and repeat until no [ is left.

No recursion at all, and easy to check by hand.

def decode(s: str) -> str:
    """Expand every k[text] in s into text repeated k times."""
    while "[" in s:
        open_at = s.rfind("[")  # the last [ has no [ after it, so nothing inside it
        close_at = s.index("]", open_at)
        start = open_at
        while start > 0 and s[start - 1].isdigit():
            start -= 1
        times = int(s[start:open_at])
        s = s[:start] + s[open_at + 1 : close_at] * times + s[close_at + 1 :]
    return s

Time

O(b · m)

Space

O(m)

Why

Each of the b bracket pairs rebuilds the whole text, which grows up to m characters, the length of the answer.

Where it breaks: 2[ab] 100,000 times has 100,000 brackets, and each pass copies text hundreds of thousands of characters long: billions of copies. It runs out of time.

Better

A call for each [

The idea: Read s left to right. Letters go into the answer, and digits build the number. A [ starts a call that decodes up to its ], then returns the text and where it stopped.

The waste in Okay: it rebuilt all of s for every bracket. Reading s once, with a call for each bracket, builds each piece once. This is the shape of most recursion on nested things: what’s inside the brackets is a smaller copy of the whole problem.

Highlighted lines are new in this rung.

def decode(s: str) -> str:
    """Expand every k[text] in s into text repeated k times."""
    text, _ = read(s, 0)
    return text


def read(s: str, i: int) -> tuple[str, int]:
    """Decode s from i to the ] that ends this part. Returns the text, and where to go on."""
    parts = []
    times = 0
    while i < len(s) and s[i] != "]":
        if s[i].isdigit():
            times = times * 10 + int(s[i])
            i += 1
        elif s[i] == "[":
            inner, i = read(s, i + 1)  # a call for each [ inside
            parts.append(inner * times)
            times = 0
        else:
            parts.append(s[i])
            i += 1
    return "".join(parts), i + 1

Time

O(m)was O(b · m)

Space

O(m)

Why

Each character of s is read once, and each piece of the answer is built once. The calls in progress are one for each [ still open.

What changed from the previous rung

def decode(s: str) -> str:
    """Expand every k[text] in s into text repeated k times."""
    while "[" in s:
        open_at = s.rfind("[")  # the last [ has no [ after it, so nothing inside it
        close_at = s.index("]", open_at)
        start = open_at
        while start > 0 and s[start - 1].isdigit():
            start -= 1
        times = int(s[start:open_at])
        s = s[:start] + s[open_at + 1 : close_at] * times + s[close_at + 1 :]
    return s
    text, _ = read(s, 0)
    return text


def read(s: str, i: int) -> tuple[str, int]:
    """Decode s from i to the ] that ends this part. Returns the text, and where to go on."""
    parts = []
    times = 0
    while i < len(s) and s[i] != "]":
        if s[i].isdigit():
            times = times * 10 + int(s[i])
            i += 1
        elif s[i] == "[":
            inner, i = read(s, i + 1)  # a call for each [ inside
            parts.append(inner * times)
            times = 0
        else:
            parts.append(s[i])
            i += 1
    return "".join(parts), i + 1

Where it breaks: 3,000 brackets inside each other need 3,000 calls in progress: RecursionError.

Best

Your own stack of open brackets

The idea: On [, put the parts so far and the number on a list, and start fresh. On ], take them off, and add the inner text repeated. The list does what the calls did.

The waste in Better: none in work. It’s the same steps, but the open brackets wait in a list instead of on Python’s call stack, so only memory limits the depth.

Highlighted lines are new in this rung.

def decode(s: str) -> str:
    """Expand every k[text] in s into text repeated k times."""
    stack = []  # for each [ still open: the parts before it, and its number
    parts: list[str] = []
    times = 0
    for c in s:
        if c.isdigit():
            times = times * 10 + int(c)
        elif c == "[":
            stack.append((parts, times))
            parts, times = [], 0
        elif c == "]":
            before, k = stack.pop()
            before.append("".join(parts) * k)
            parts = before
        else:
            parts.append(c)
    return "".join(parts)

Time

O(m)

Space

O(m)

Why

Each character is read once, and each piece built once. The list holds one entry for each [ still open.

What changed from the previous rung

def decode(s: str) -> str:
    """Expand every k[text] in s into text repeated k times."""
    text, _ = read(s, 0)
    return text


def read(s: str, i: int) -> tuple[str, int]:
    """Decode s from i to the ] that ends this part. Returns the text, and where to go on."""
    parts = []
    stack = []  # for each [ still open: the parts before it, and its number
    parts: list[str] = []
    times = 0
    while i < len(s) and s[i] != "]":
        if s[i].isdigit():
            times = times * 10 + int(s[i])
            i += 1
        elif s[i] == "[":
            inner, i = read(s, i + 1)  # a call for each [ inside
            parts.append(inner * times)
            times = 0
    for c in s:
        if c.isdigit():
            times = times * 10 + int(c)
        elif c == "[":
            stack.append((parts, times))
            parts, times = [], 0
        elif c == "]":
            before, k = stack.pop()
            before.append("".join(parts) * k)
            parts = before
        else:
            parts.append(s[i])
            i += 1
    return "".join(parts), i + 1
            parts.append(c)
    return "".join(parts)

When Best isn’t best: Better is easier to follow, and real inputs are rarely 1,000 brackets deep. Either way, the answer can be huge: 9[9[9[9[9[9[a]]]]]] is 19 characters, and decodes to 531,441.

3. The k-th symbol in a row (medium)

Row 1 is 0. To make each next row, write 01 for every 0 in the row above, and 10 for every 1. So row 2 is 01, row 3 is 0110, and row 4 is 01101001. Write symbol(n, k): the k-th symbol of row n, counting from 1, as the number 0 or 1.

Example: symbol(4, 5) gives 1, the 5th symbol of 01101001.

Hint 1 of 3

Building the rows works, but each row is twice as long as the last: row 40 has over 500 billion symbols.

Hint 2 of 3

Symbol k of row n was made by symbol (k + 1) // 2 of the row above. The first of each pair is a copy of it, and the second is flipped. That’s a smaller copy of the same question.

Hint 3 of 3

Each call makes just one call, and only flips what comes back. So a loop can do it: walk k up to row 1, counting the flips.

The k-th symbol in a row

Ctrl + Enter runs

def symbol(n: int, k: int) -> int: # Symbol k (from 1) of row n. Row 1 is 0, then # each 0 becomes 01 and each 1 becomes 10. return 0

Run testsVisualizeReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: symbol(1, 1) → 0
2. ○Not run yet: symbol(2, 2) → 1
3. ○Not run yet: symbol(4, 5) → 1
4. ○Not run yet: Extra test
5. ○Not run yet: Extra test
6. ○Not run yet: Speed test: the last symbol of row 40 → 1
7. ○Not run yet: Row 5,000 → 0

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

symbol()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Build every row

The idea: Start with '0', and build each row from the one above, n − 1 times. Then read symbol k.

It does exactly what the question says.

def symbol(n: int, k: int) -> int:
    """Symbol k (from 1) of row n. Row 1 is 0, then each 0 becomes 01 and each 1 becomes 10."""
    row = "0"
    for _ in range(n - 1):
        row = "".join("01" if c == "0" else "10" for c in row)
    return int(row[k - 1])

Time

O(2ⁿ)

Space

O(2ⁿ)

Why

Each row is twice as long as the one above, so row n has 2ⁿ⁻¹ symbols, and building it reads all of the row above.

Where it breaks: row 40 has 549,755,813,888 symbols. Building it would take hours, and more memory than the computer has.

Better

Ask the row above

The idea: Symbol k of row n came from symbol (k + 1) // 2 of row n − 1: the same when k is odd, flipped when k is even. Row 1 is the base case: 0.

The waste in Okay: it builds every symbol, when only one line of parents leads to symbol k.

Highlighted lines are new in this rung.

def symbol(n: int, k: int) -> int:
    """Symbol k (from 1) of row n. Row 1 is 0, then each 0 becomes 01 and each 1 becomes 10."""
    if n == 1:
        return 0
    parent = symbol(n - 1, (k + 1) // 2)  # the symbol in the row above that made it
    return parent if k % 2 == 1 else 1 - parent

Time

O(n)was O(2ⁿ)

Space

O(n)was O(2ⁿ)

Why

One call for each row, from n up to 1, and all n are in progress at once.

What changed from the previous rung

def symbol(n: int, k: int) -> int:
    """Symbol k (from 1) of row n. Row 1 is 0, then each 0 becomes 01 and each 1 becomes 10."""
    row = "0"
    for _ in range(n - 1):
        row = "".join("01" if c == "0" else "10" for c in row)
    return int(row[k - 1])
    if n == 1:
        return 0
    parent = symbol(n - 1, (k + 1) // 2)  # the symbol in the row above that made it
    return parent if k % 2 == 1 else 1 - parent

Where it breaks: row 5,000 needs 5,000 calls in progress: RecursionError.

Best

Walk up with a loop

The idea: Walk k up to row 1 in a loop, counting the flips: one each time k is even. An odd number of flips gives 1.

The waste in Better: each call waits only to flip what comes back, so the calls in progress hold nothing a count can’t. When a call makes one call and only adjusts the answer, a loop can replace it, with no stack at all.

Highlighted lines are new in this rung.

def symbol(n: int, k: int) -> int:
    """Symbol k (from 1) of row n. Row 1 is 0, then each 0 becomes 01 and each 1 becomes 10."""
    flips = 0
    for _ in range(n - 1):
        if k % 2 == 0:
            flips += 1  # the second of a pair is its parent flipped
        k = (k + 1) // 2  # go up to the parent
    return flips % 2

Time

O(n)

Space

O(1)was O(n)

Why

One step for each row, keeping only k and a count, however big n is.

What changed from the previous rung

def symbol(n: int, k: int) -> int:
    """Symbol k (from 1) of row n. Row 1 is 0, then each 0 becomes 01 and each 1 becomes 10."""
    if n == 1:
        return 0
    parent = symbol(n - 1, (k + 1) // 2)  # the symbol in the row above that made it
    return parent if k % 2 == 1 else 1 - parent
    flips = 0
    for _ in range(n - 1):
        if k % 2 == 0:
            flips += 1  # the second of a pair is its parent flipped
        k = (k + 1) // 2  # go up to the parent
    return flips % 2

When Best isn’t best: there’s a shortcut. Each flip is a 1 in k − 1 written in binary, so bin(k - 1).count('1') % 2 is the answer. It’s one line, but much harder to explain in an interview than the walk up.

Check yourself

A few quick questions. Ones you miss are remembered, so you can find your weak spots later.

1. Predict the outputWhat does this print?

   def count_down(n):
       if n == 0:
           return []
       return [n] + count_down(n - 1)
   
   print(count_down(3))

   [3, 2, 1][1, 2, 3][3, 2, 1, 0]RecursionError

   Check answer
2. Spot the bugThis adds up a list of numbers. What goes wrong?

   def total(nums):
       return nums[0] + total(nums[1:])

   It adds the first number twiceIndexError when the list runs outIt's O(log n)Nothing

   Check answer
3. Multiple choicef(n) calls f(n // 2) twice, does a little other work, and stops at n = 0. About how many calls does f(1000) make?

   About 10About 1,000About 2,000About 1,000,000

   Check answer
4. Multiple choiceWhy does Python raise RecursionError at about 1,000 calls deep?

   Each call in progress holds memory, so Python limits how many there can beA program can only make 1,000 calls in allRecursion is slower than a loopThe base case is missing

   Check answer
5. Predict the outputWhat does this print?

   def walk(n, seen=[]):
       seen.append(n)
       if n > 0:
           walk(n - 1)
       return len(seen)
   
   print(walk(2))
   print(walk(2))

   3, then 33, then 61, then 1RecursionError

   Check answer

Flashcards

Add these to your review deck. Each card comes back a little later every time you get it right.

• Card 1What two parts does every recursive function need?Show answer
• Card 2What is the call stack?Show answer
• Card 3When does Python raise RecursionError?Show answer
• Card 4How do you count a recursive function's work?Show answer
• Card 5f(n) calls f(n // 2) once, or twice. How many calls in all?Show answer
• Card 6How do you turn a recursion into a loop?Show answer

Add 6 cards to my review deck

Cheat sheet

• Recursion: a base case, and a step that calls itself on something smaller. Every input must reach the base case.
• Each call waits for the one it made, and the answers come back up in reverse order.
• Python allows about 1,000 calls in progress: past that, RecursionError.
• Draw the calls as a tree. The calls in all are the time; the deepest line is the memory.
• Halving n gives about log₂ n rows. Calling twice on each row doubles them: about 2n calls.
• Work out a repeated call once, and keep the answer in a variable.
• f(nums[1:]) copies the list every call: O(n²). Pass an index.
• Python never turns a last call into a loop. For deep inputs, use a loop and your own list as a stack.
• Never a mutable default, like seen=[], in a recursive function.

Go deeper

• In the Python docs: sys.getrecursionlimit(), and functools.cache, which keeps a function’s answers so a call is never worked out twice.
• Draw your own: the Call tree pictures on the DSA visualizer.
• My server ignored the port I set follows an error up through the calls in progress.
• Next on the DSA roadmap: basic sorting.

Can you do these now?

If you’re not sure of any of these, scroll back to that part before moving on.

• Write a recursive function with a base case and a step that gets smaller
• Say how many calls are in progress at once, and why too many raise RecursionError
• Count a recursive function’s calls by drawing them as a tree
• Turn a recursion into a loop, with your own stack when it needs one

✓Mark as completeI already know this

Status: Not started