Skip to content
LumenaryAcademy
Core 75 min

Recursion and divide and conquer

Functions that call themselves, the call stack that makes it work, and how to solve a problem by splitting it.

Code tested · 8AI-draftedAwaiting review by a computer scientist

Your guides: Chloe · The Computer Scientist, Margaret · The Experimenter, Gideon · The Verifier

MotivationH

Problems that contain themselves

How many files are in a folder? You can't just count the files you see, because some of the things in the folder are other folders, which contain files and more folders, and so on, as deep as you like. But there is a short answer:

The number of files in a folder is the number of files directly inside it, plus, for each folder inside it, the number of files in that folder.

The definition uses itself, yet it isn't circular, because each use is about a smaller folder, and eventually you reach folders with no subfolders, where the answer is just a count. That is recursion: solving a problem by solving smaller instances of the same problem.

Recursion is everywhere once you look. A family tree: your ancestors are your parents and the ancestors of your parents. A Russian matryoshka doll: a doll that may contain a smaller doll, which may contain a smaller one. A sentence in any human language can contain a clause that is itself a sentence. And data in computing is full of it: folders, web pages made of nested elements, expressions like (2 + 3) * (4 - 1) made of smaller expressions, the trees and graphs of the lessons ahead.

This lesson shows how a function can call itself, what Python does to make that work, how to be sure a recursive function is correct and finishes, and how the strategy of divide and conquer (split a problem into parts, solve each part recursively, combine the answers) leads to some of the fastest algorithms known. You'll also learn the tool for analysing such algorithms: recurrences and the master theorem.

IntuitionH

Trust the smaller problem

Analogy, not a formal construction

You are in a long queue at a stadium in Dakar and want to know your position. You can't see the front. So you ask the person ahead: "What's your position?" They don't know either, so they ask the person ahead of them, and so on, until the question reaches the person at the front, who says "1". The answers then travel back: "2", "3", …, until the person ahead of you says "57", and you know you are 58th. Nobody had to see the whole queue; each person did one tiny step and trusted the answer from the person in front.

The analogy has every ingredient of a recursive function:

  • a base case that is answered directly (the person at the front says "1");
  • a recursive case that reduces the problem to a smaller one of the same kind (ask the person ahead) and builds the answer from it (add 1);
  • progress: each question is about a queue one person shorter, so the questions must reach the front.

The hardest part for most learners is the middle step, which needs a kind of trust. When you write the recursive case, assume the recursive call returns the right answer for the smaller problem, and only ask: "given that, do I compute the right answer for this one?" This is not wishful thinking; it is exactly the induction hypothesis in a proof by induction, and we'll make it rigorous shortly.

DefinitionsH

Definitions

Definition— recursive function

A function is recursive if it calls itself, directly or through other functions. A recursive function has one or more base cases, inputs it answers without recursion, and one or more recursive cases, which call the function on smaller inputs and combine the results.

Definition— termination measure

A termination measure for a recursive function is a quantity, computed from the arguments, that is a natural number and strictly decreases with every recursive call (for example nn, or the length of a list). If such a measure exists and every input at which it can no longer decrease is a base case, the recursion always stops.

Definition— call stack

Each call that has started but not yet returned has a stack frame: a record of its local variables and of where to resume when the call it is waiting for returns. The frames form the call stack: a new call pushes a frame on top; a return pops it off. Only the top frame is running.

Worked examplesH

First recursive functions

The factorial n!=1×2×⋯×nn! = 1 \times 2 \times \dots \times n (with 0!=10! = 1) satisfies n!=n×(n−1)!n! = n \times (n-1)! for n≥1n \ge 1. That identity is a recursive algorithm:

python
def factorial(n):
    if n == 0:                       # base case
        return 1
    return n * factorial(n - 1)      # recursive case: a smaller n

Theorem— factorial is correct

For every integer n≥0n \ge 0, factorial(n) terminates and returns n!n!.

Proof

By induction on nn (see proof techniques). Base: factorial(0) returns 1, which is 0!0!. Step: let n≥1n \ge 1 and assume factorial(n - 1) terminates and returns (n−1)!(n-1)!. Then factorial(n) reaches the recursive case, which returns n⋅(n−1)!=n!n \cdot (n-1)! = n!. Termination follows because nn is a natural number that decreases by 1 at each call and the base case covers 0.

∎

The proof is exactly the "trust" from the intuition section: the induction hypothesis is the trust, and the proof checks the one step. Notice what it does not cover: factorial(-1) calls factorial(-2), and so on, never reaching the base case. The measure nn stops being a natural number, and the theorem's hypothesis n≥0n \ge 0 was there for a reason. A careful function would reject negative input with a ValueError.

The same pattern works on lists. The sum of a list is 0 if the list is empty, and otherwise the first item plus the sum of the rest:

python
def total(xs):
    if not xs:
        return 0
    return xs[0] + total(xs[1:])

This is correct, but beware a hidden cost: xs[1:] copies the rest of the list, so each call does Θ(n)\Theta(n) work and the whole sum costs Θ(n2)\Theta(n^2). Passing a start index instead of slicing avoids the copies. (In practice, of course, use sum or a loop for this; it's an example of the pattern, not the best way to add numbers.)

ExplanationH

What Python does: the call stack

When factorial(4) runs, it reaches 4 * factorial(3) and must wait: it can't multiply until it knows factorial(3). Python saves its place (a stack frame holding n = 4 and "resume at the multiplication") and starts the call factorial(3), which in turn waits for factorial(2), and so on. At the deepest point, five frames are on the stack, for n=4,3,2,1,0n = 4, 3, 2, 1, 0. Then factorial(0) returns 1, its frame is popped, factorial(1) resumes and returns 1⋅11 \cdot 1, and the answers flow back up: 1, 2, 6, 24.

The program below prints this process. Each call is indented by its depth, so you can see the stack grow and shrink.

python
def factorial(n, depth=0):
    pad = "    " * depth
    print(f"{pad}factorial({n}) starts")
    if n == 0:
        result = 1
    else:
        result = n * factorial(n - 1, depth + 1)
    print(f"{pad}factorial({n}) returns {result}")
    return result

factorial(4)
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Two consequences matter in practice.

  • Recursion uses memory. The stack holds one frame per unfinished call, so a recursion of depth dd uses Θ(d)\Theta(d) memory even if each frame is small. factorial(n) uses Θ(n)\Theta(n) memory; the loop version uses Θ(1)\Theta(1).
  • There is a limit. Python refuses to let the stack grow without bound. By default, standard CPython allows about 1000 nested calls (sys.getrecursionlimit() tells you the current limit; other environments, including browsers, may set a different value). Beyond it, Python raises RecursionError: maximum recursion depth exceeded. So factorial(5000) fails in a default CPython, while a loop computes it instantly.
Worked examplesH

Recursion follows the shape of the data

Recursion is most natural when the data is recursive. A list whose items may themselves be lists is like the folder at the start of the lesson, and the code mirrors its definition:

python
def deep_sum(item):
    """Sum all the numbers in item, which is a number or a list of items."""
    if not isinstance(item, list):       # base case: a plain number
        return item
    total = 0
    for part in item:                    # recursive case: add up the parts
        total += deep_sum(part)
    return total

print(deep_sum([1, [2, 3], [[4], [], 5]]))     # 15

# A folder is a dictionary with a number of files and a list of subfolders
home = {"files": 3, "folders": [
    {"files": 10, "folders": []},
    {"files": 1, "folders": [
        {"files": 4, "folders": []},
        {"files": 0, "folders": [{"files": 7, "folders": []}]},
    ]},
]}

def count_files(folder):
    return folder["files"] + sum(count_files(sub) for sub in folder["folders"])

print(count_files(home))                     # 3 + 10 + 1 + 4 + 0 + 7 = 25
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Writing deep_sum with loops alone is awkward, because you don't know in advance how deeply the lists are nested; the recursive version handles any depth for free. The termination measure is the nesting depth: each call is on a strictly smaller piece of the structure. Trees, which you'll meet in Trees, are processed this way almost always.

Worked examplesH

Fibonacci, and the cost of repeating yourself

The Fibonacci numbers are defined by F0=0F_0 = 0, F1=1F_1 = 1 and Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2} for n≥2n \ge 2: 0, 1, 1, 2, 3, 5, 8, 13, 21, … They are named after Leonardo of Pisa, called Fibonacci, whose Liber Abaci (1202) posed a puzzle about breeding rabbits that leads to them. But they were known centuries earlier in India, where scholars of Sanskrit poetry, including Virahāṅka and later Hemacandra, counted the rhythms that can be made from short syllables (one beat) and long syllables (two beats): the number of rhythms with nn beats is Fn+1F_{n+1}.

The definition translates directly into code:

python
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

It is correct, by the same kind of induction as for factorial. It is also catastrophically slow: fib(40) takes many seconds in Python, and fib(100) would not finish in your lifetime. The reason is visible in its recursion tree:

f(5)f(4)f(3)f(2)f(1)f(0)f(1)f(2)f(1)f(0)f(3)f(2)f(1)f(0)f(1)
The calls made by fib(5). The same subproblems are solved again and again: f(3) twice, f(2) three times. The tree has 15 nodes, and it roughly doubles in size each time n grows by one.

Theorem— naive Fibonacci makes exponentially many calls

Let C(n)C(n) be the number of calls made by fib(n), including the first. Then C(n)=2Fn+1−1C(n) = 2F_{n+1} - 1.

Proof

C(0)=C(1)=1C(0) = C(1) = 1, and 2F1−1=2F2−1=12F_1 - 1 = 2F_2 - 1 = 1. For n≥2n \ge 2, a call makes itself plus all the calls of its two subcalls: C(n)=1+C(n−1)+C(n−2)C(n) = 1 + C(n-1) + C(n-2). Assuming the formula for n−1n - 1 and n−2n - 2, this is 1+(2Fn−1)+(2Fn−1−1)=2(Fn+Fn−1)−1=2Fn+1−11 + (2F_n - 1) + (2F_{n-1} - 1) = 2(F_n + F_{n-1}) - 1 = 2F_{n+1} - 1.

∎

Since FnF_n grows like φn/5\varphi^n / \sqrt{5}, where φ=(1+5)/2≈1.618\varphi = (1 + \sqrt{5})/2 \approx 1.618 is the golden ratio, the running time is Θ(φn)\Theta(\varphi^n): exponential. Yet there are only n+1n + 1 different subproblems, F0F_0 to FnF_n. The waste is all repetition.

Two standard fixes:

  • Memoisation: keep a dictionary of answers already computed, and look there before recomputing. Each FkF_k is then computed once, so the time is Θ(n)\Theta(n). Python's functools.cache decorator adds this to a function in one line.
  • Iteration from the bottom up: compute F0,F1,F2,…F_0, F_1, F_2, \dots in order, keeping only the last two: Θ(n)\Theta(n) time and Θ(1)\Theta(1) memory.

Both are the starting points of Dynamic programming, one of the most powerful techniques in algorithm design.

python
from functools import cache
import time

calls = 0
def fib_naive(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

@cache
def fib_memo(n):
    if n < 2:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

def fib_loop(n):
    a, b = 0, 1              # F(0), F(1)
    for _ in range(n):
        a, b = b, a + b
    return a

for n in [10, 20, 25]:
    calls = 0
    start = time.perf_counter()
    value = fib_naive(n)
    ms = (time.perf_counter() - start) * 1000
    print(f"fib({n}) = {value}: {calls} calls, {ms:.1f} ms")

print(fib_memo(90), fib_loop(90))      # instant
print(fib_loop(1000) % 10**10, "(last ten digits of F(1000))")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

The global variable calls is used here only to count; the global statement lets the function update it.

ExplanationH

Recursion or iteration?

Every recursive function can be rewritten with loops, if necessary by keeping your own explicit stack (a list of pending work) in place of Python's call stack; and every loop can be written as a recursion. So the choice is about clarity, efficiency and limits, not about what is possible.

  • Use recursion when the problem has a recursive shape: nested data, trees, divide and conquer. The recursive code is usually shorter and closer to the definition, and its correctness proof is a straightforward induction. The depth is usually small, often Θ(log⁡n)\Theta(\log n).
  • Use a loop for simple linear repetition, like summing a list or counting down. The loop needs no stack frames, so it is faster in Python and never hits the recursion limit.

Some languages (Scheme, for example, and many functional languages) guarantee tail-call elimination: if the recursive call is the very last thing a function does, the language reuses the current frame, so such recursions use constant memory, like loops. Python deliberately does not do this. Guido van Rossum, Python's creator, explained why in a 2009 post: it would make tracebacks less informative, and he preferred to keep recursion for problems that genuinely need it.

What about the recursion limit? You can raise it with sys.setrecursionlimit, but cautiously: the limit exists to stop runaway recursion from exhausting the memory set aside for the stack, which can crash the interpreter outright instead of raising a tidy exception. If you need recursion thousands of levels deep, that is usually a sign to write a loop.

python
import sys
print(sys.getrecursionlimit())     # 1000 in a default CPython

def count_down(n):
    if n == 0:
        return "done"
    return count_down(n - 1)

count_down(500)       # fine
count_down(100_000)   # RecursionError: maximum recursion depth exceeded
Worked examplesH

Divide and conquer

Divide and conquer is a recursive strategy with three steps:

  1. Divide the problem into smaller subproblems, typically of a constant fraction of the size (often half).
  2. Conquer each subproblem recursively (very small ones directly).
  3. Combine the subproblems' answers into an answer for the whole.

Example— Fast exponentiation

To compute xnx^n, the obvious loop does n−1n - 1 multiplications. But xn=(xn/2)2x^{n} = (x^{n/2})^2 when nn is even, and xn=x⋅(x(n−1)/2)2x^n = x \cdot (x^{(n-1)/2})^2 when nn is odd. So one recursive call on ⌊n/2⌋\lfloor n/2 \rfloor, one squaring and perhaps one more multiplication do the job. The exponent halves each time, so there are about log⁡2n\log_2 n levels and at most about 2log⁡2n2 \log_2 n multiplications: the code below computes x1000x^{1000} with 16 multiplications instead of 999. Python's built-in pow uses a form of this idea, and it is how cryptographic software computes the huge powers that Applied cryptography relies on.

Example— Multiplying big numbers

Schoolbook multiplication of two nn-digit numbers takes Θ(n2)\Theta(n^2) digit operations. Splitting each number into a high half and a low half, x=x1B+x0x = x_1 B + x_0 and y=y1B+y0y = y_1 B + y_0 with BB a power of the base, gives xy=x1y1B2+(x1y0+x0y1)B+x0y0xy = x_1 y_1 B^2 + (x_1 y_0 + x_0 y_1) B + x_0 y_0: four half-size products, which turns out to be no faster. In 1960 Anatoly Karatsuba, then a student in Moscow, noticed that x1y0+x0y1=(x1+x0)(y1+y0)−x1y1−x0y0x_1 y_0 + x_0 y_1 = (x_1 + x_0)(y_1 + y_0) - x_1 y_1 - x_0 y_0, so three half-size products suffice. That small saving, applied at every level of the recursion, gives Θ(nlog⁡23)≈Θ(n1.585)\Theta(n^{\log_2 3}) \approx \Theta(n^{1.585}), and CPython uses Karatsuba's method when it multiplies very large integers.

The next lesson, Searching and sorting, uses divide and conquer for binary search, merge sort and quicksort.

python
def power_slow(x, n):
    """Return (x ** n, number of multiplications), multiplying n - 1 times."""
    result, mults = x, 0
    for _ in range(n - 1):
        result = result * x
        mults += 1
    return result, mults

def power_fast(x, n):
    """Return (x ** n, number of multiplications), by repeated squaring."""
    if n == 0:
        return 1, 0
    half, mults = power_fast(x, n // 2)
    result = half * half
    mults += 1
    if n % 2 == 1:
        result = result * x
        mults += 1
    return result, mults

for n in [10, 100, 1000, 100_000]:
    value, m_fast = power_fast(3, n)
    assert value == 3 ** n
    if n <= 1000:
        _, m_slow = power_slow(3, n)
        print(f"3^{n}: slow {m_slow} multiplications, fast {m_fast}")
    else:
        print(f"3^{n}: fast {m_fast} multiplications (the result has {value.bit_length()} bits)")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.
Worked examplesH

Recurrences and the master theorem

The running time of a recursive algorithm is naturally described by a recurrence: an equation that gives T(n)T(n) in terms of TT at smaller sizes. Fast exponentiation does one call on half the input plus constant work: T(n)=T(n/2)+Θ(1)T(n) = T(n/2) + \Theta(1). An algorithm that splits into two halves and does linear work to combine, like merge sort, has T(n)=2T(n/2)+Θ(n)T(n) = 2T(n/2) + \Theta(n). (Strictly, sizes are rounded, T(⌊n/2⌋)T(\lfloor n/2 \rfloor), and T(n)=Θ(1)T(n) = \Theta(1) for small nn; these details don't change the answers here.)

Recursion trees

The most illuminating way to solve such a recurrence is to draw its recursion tree and add up the work level by level. For T(n)=2T(n/2)+nT(n) = 2T(n/2) + n:

nn/2n/2n/4n/4n/4n/4n/8n/8n/8n/8n/8n/8n/8n/8⋮n subproblems of size 1n2 · n/2 = n4 · n/4 = n8 · n/8 = nn · 1 = n
The recursion tree of T(n) = 2T(n/2) + n. Level i has 2^i subproblems of size n/2^i, so every level costs n in total. With about log₂ n + 1 levels, the total is Θ(n log n).

The same method works in general. For T(n)=a T(n/b)+ndT(n) = a\,T(n/b) + n^d, level ii of the tree has aia^i subproblems, each of size n/bin / b^i, so its total work is

ai(nbi)d=nd(abd)i,a^i \left( \frac{n}{b^i} \right)^d = n^d \left( \frac{a}{b^d} \right)^i,

and there are about log⁡bn\log_b n levels. The level costs form a geometric series with ratio q=a/bdq = a / b^d. Everything depends on whether that ratio is below, equal to, or above 1, which gives the three cases of the master theorem.

Theorem— The master theorem (polynomial form)

Let a≥1a \ge 1, b>1b > 1 and d≥0d \ge 0 be constants, and suppose T(n)=a T(n/b)+Θ(nd)T(n) = a\,T(n/b) + \Theta(n^d) for large nn (with n/bn/b rounded up or down), and T(n)=Θ(1)T(n) = \Theta(1) for small nn. Then

  • if d>log⁡bad > \log_b a, then T(n)=Θ(nd)T(n) = \Theta(n^d);
  • if d=log⁡bad = \log_b a, then T(n)=Θ(ndlog⁡n)T(n) = \Theta(n^d \log n);
  • if d<log⁡bad \lt \log_b a, then T(n)=Θ(nlog⁡ba)T(n) = \Theta(n^{\log_b a}).

The intuition, from the geometric series: if q<1q \lt 1 (that is, d>log⁡bad > \log_b a), the costs shrink going down the tree and the root's ndn^d dominates. If q=1q = 1, all Θ(log⁡n)\Theta(\log n) levels cost the same ndn^d. If q>1q > 1, the costs grow going down and the leaves dominate; there are alog⁡bn=nlog⁡baa^{\log_b n} = n^{\log_b a} of them. A full proof sums the series carefully and handles the rounding; the textbook versions also allow more general combining costs f(n)f(n) in place of ndn^d.

AlgorithmRecurrenceaa, bb, ddResult
binary search, fast powerT(n/2)+1T(n/2) + 11, 2, 0Θ(log⁡n)\Theta(\log n)
maximum by halves2T(n/2)+12T(n/2) + 12, 2, 0Θ(n)\Theta(n)
merge sort2T(n/2)+n2T(n/2) + n2, 2, 1Θ(nlog⁡n)\Theta(n \log n)
Karatsuba multiplication3T(n/2)+n3T(n/2) + n3, 2, 1Θ(nlog⁡23)≈Θ(n1.585)\Theta(n^{\log_2 3}) \approx \Theta(n^{1.585})
four half-size products4T(n/2)+n4T(n/2) + n4, 2, 1Θ(n2)\Theta(n^2)
Strassen's matrix multiplication7T(n/2)+n27T(n/2) + n^27, 2, 2Θ(nlog⁡27)≈Θ(n2.81)\Theta(n^{\log_2 7}) \approx \Theta(n^{2.81})

The master theorem does not apply when the subproblems shrink by subtraction rather than division. Those recurrences can usually be solved by unrolling them: T(n)=T(n−1)+nT(n) = T(n-1) + n gives n+(n−1)+⋯+1=Θ(n2)n + (n-1) + \dots + 1 = \Theta(n^2), and T(n)=2T(n−1)+1T(n) = 2T(n-1) + 1 gives 2n−12^n - 1, which is the number of moves in the Tower of Hanoi, a puzzle published by the French mathematician Édouard Lucas in 1883 (one of the exercises asks you to solve it). For much more on solving recurrences, see Recurrences and generating functions in Lumenary Math.

Common misconceptionsH

Common mistakes

Misconception

A base case that can be skipped. def f(n): return 1 if n == 0 else f(n - 2) works for even nn but runs past 0 for odd nn. Check that the termination measure can only ever arrive at a base case: here n <= 0 would be safe.

Misconception

"Recursion is slow" or "recursion is elegant, so it's better". Neither. Naive Fibonacci is slow because it repeats work, not because it is recursive; merge sort is recursive and fast. A recursion is as efficient as the algorithm it expresses, plus a modest cost per call.

Misconception

"Recursion uses no memory." Every unfinished call holds a stack frame. A recursion of depth nn uses Θ(n)\Theta(n) memory, and in Python it hits the recursion limit at a depth of about a thousand by default.

Misconception

"The master theorem solves every recurrence." It covers T(n)=aT(n/b)+f(n)T(n) = aT(n/b) + f(n) with equal-sized parts shrinking by a constant factor. It does not cover T(n)=T(n−1)+nT(n) = T(n-1) + n, or uneven splits like T(n/3)+T(2n/3)+nT(n/3) + T(2n/3) + n; for those, use recursion trees or substitution.

Exercises

Exercises

1. Recursion and divide and conquer

Warm-upHuman

The naive function

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

is called as fib(10). How many calls of fib happen in total, including the first one? (Use F0=0,F1=1,F2=1,…F_0 = 0, F_1 = 1, F_2 = 1, \dots)

2. Recursion and divide and conquer

CoreHuman

Solve T(n)=4 T(n/2)+n2T(n) = 4\,T(n/2) + n^2.

Choose one

3. Recursion and divide and conquer

CoreHuman

Karatsuba's algorithm splits each nn-digit number in half and makes three recursive multiplications of half size, plus Θ(n)\Theta(n) additions and shifts. Its running time is:

Choose one

4. Recursion and divide and conquer

CoreComputational

Which of these functions fails to terminate for some whole number n≥0n \ge 0?

Choose one

5. Recursion and divide and conquer

CoreComputational

Write a recursive power(x, n) that returns xnx^n for a whole number n≥0n \ge 0, using at most about 2log⁡2n2 \log_2 n multiplications, by repeated squaring:

  • x0=1x^0 = 1;
  • if nn is even, xn=(xn/2)2x^n = (x^{n/2})^2;
  • if nn is odd, xn=x⋅(x(n−1)/2)2x^n = x \cdot (x^{(n-1)/2})^2.

Don't use ** or pow. The checker counts your multiplications: computing a power with n=1000n = 1000 may use at most 22.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

6. Recursion and divide and conquer

CoreComputational

Write flatten(nested) that takes a list whose items are numbers or (nested) lists, and returns a flat list of all the numbers, in order, however deeply they are nested:

flatten([1, [2, [3, 4]], [], [[5]]]) == [1, 2, 3, 4, 5]

The starter only handles one level of nesting. Use isinstance(item, list) to tell lists from numbers.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

7. Recursion and divide and conquer

CoreComputational

In the Tower of Hanoi, nn discs of different sizes sit on peg source, largest at the bottom. Move them all to peg target, one disc at a time, never putting a larger disc on a smaller one, using peg spare as well.

Write hanoi(n, source, target, spare) that returns the list of moves, each a tuple (from_peg, to_peg). The recursive idea: move the top n−1n - 1 discs out of the way to spare, move the largest disc to target, then move the n−1n - 1 discs from spare onto it.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

8. Recursion and divide and conquer

StretchComputational

Sanskrit poets counted rhythms made of short syllables (1 beat, written S) and long syllables (2 beats, written L). Write a recursive rhythms(n) that returns a list of all the strings of S and L whose beats add up to exactly n. For example, rhythms(3) contains "SSS", "SL" and "LS" (in any order), and rhythms(0) is [""]: one rhythm, the empty one.

Hint: a rhythm of nn beats starts either with S followed by a rhythm of n−1n - 1 beats, or with L followed by a rhythm of n−2n - 2 beats.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Further reading and resources