Unit 9 — Recursion & Backtracking

Slide 1 of 36

How many ways can you choose some of the numbers 4 3 1 2 so they add up to exactly 5? (Two: 4+1 and 3+2.) Listing them by hand is easy for four numbers, but the choices DOUBLE with every extra number. Recursion solves one smaller decision at a time; backtracking tries a choice, explores where it leads, then backs up to try the next — so we can COUNT every valid answer. We build it as a short ladder of executable demos (each with a Notice), then a full stdin solver.
- Write a recursive function with a base case and a recursive case.
- Trace how the call stack unwinds as the calls return.
- Use backtracking: make a choice, recurse, then undo it to try the next choice.
- Evaluate a nested parenthesized expression by recursion.
Lesson 1 — A Function Solving a Smaller Copy

Factorial: the base case 0! = 1, the recursive case n! = n * (n-1)!.

data = '6'
n = int(data.strip())

def factorial(value):
    if value == 0:
        return 1
    return value * factorial(value - 1)

print(str(factorial(n)))

Output

Each call reduces value by 1 until the base case 0 stops the recursion; 6! = 720.

The CALL STACK unwinds in reverse: countdown builds its answer as the calls return.

data = '4'
n = int(data.strip())

def countdown(value):
    if value == 0:
        return "GO"
    return str(value) + " " + countdown(value - 1)

print(countdown(n))

Output

4 3 2 1 GO

The recursive call happens BEFORE the concatenation, so GO (the base case) is reached first and the numbers attach as the stack unwinds.

Accumulate THROUGH the returns: a recursive sum of a list adds values[index] to the sum of the rest.

data = '4 7 6'
values = []
for token in data.split():
    values.append(int(token))

def recursive_sum(index):
    if index == len(values):
        return 0
    return values[index] + recursive_sum(index + 1)

print(str(recursive_sum(0)))

Output

recursive_sum(index) returns values[index] + recursive_sum(index+1); the base case (index past the end) returns 0.

Put it together: the program reads the numbers from stdin and prints their recursive sum.

Try it

import sys

data = sys.stdin.read()
values = []
for token in data.split():
    values.append(int(token))

def recursive_sum(index):
    if index == len(values):
        return 0
    return values[index] + recursive_sum(index + 1)

print(str(recursive_sum(0)))

Run the full solver from this unit folder:
```
python assets/l1.py < assets/l1/1.in
```
A nested recursive_sum adds each value to the sum of the remaining ones; the base case (past the end) returns 0.

Complexity: O(n) — one call per value, recursion depth n.
Lesson 2 — Try, Recurse, Undo (Backtracking)

At each index, INCLUDE the value or SKIP it, and recurse on the rest. Count the choices that hit a target.

data = '7 2 5 1 6'
tokens = data.split()
target = int(tokens[0])
values = []
for token in tokens[1:]:
    values.append(int(token))
n = len(values)

def search(index, total, path):
    if index == n:
        if total == target:
            return 1
        return 0
    with_value = search(index + 1, total + values[index], path + [values[index]])
    without_value = search(index + 1, total, path)
    return with_value + without_value

print(str(search(0, 0, [])))

Output

search explores BOTH branches — path + [value] (include) and the same path (skip) — and sums the counts; a fresh path + [value] needs no undo.
Choose an UNUSED value, marking and UN-marking it (the undo) — here counting orderings where consecutive picks differ by at least 2.

values = [1, 3, 5]
used = []
for value in values:
    used.append(False)

def search(path):
    if len(path) == len(values):
        return 1
    ways = 0
    for choice_index in range(len(values)):
        if used[choice_index] == False:
            choice = values[choice_index]
            if len(path) == 0 or abs(path[-1] - choice) >= 2:
                used[choice_index] = True
                ways = ways + search(path + [choice])
                used[choice_index] = False
    return ways

print(search([]))

Output

used[choice_index] = True before recursing and = False after is the backtracking undo (no .pop); the abs(path[-1] - choice) >= 2 guard rejects choices within 1 of the previous pick.
Choose in INCREASING index order to build combinations without repeats.

data = '5 3'
tokens = data.split()
n = int(tokens[0])
choose = int(tokens[1])

def search(next_index, path):
    if len(path) == choose:
        return 1
    ways = 0
    for choice in range(next_index, n):
        ways = ways + search(choice + 1, path + [choice])
    return ways

print(str(search(0, [])))

Output

Starting each choice at next_index avoids re-picking earlier items, so choose 3 of 5 gives 10 combinations.

Put it together: the subset-count program reads the target then the values from stdin and prints how many subsets sum to the target.

Try it

import sys

data = sys.stdin.read()
tokens = data.split()
target = int(tokens[0])
values = []
for token in tokens[1:]:
    values.append(int(token))
n = len(values)

def search(index, total, path):
    if index == n:
        if total == target:
            return 1
        return 0
    with_value = search(index + 1, total + values[index], path + [values[index]])
    without_value = search(index + 1, total, path)
    return with_value + without_value

print(str(search(0, 0, [])))

Run the full solver from this unit folder:
```
python assets/l2.py < assets/l2/1.in
```
At each index, recurse INCLUDING then EXCLUDING the value; the base case scores 1 when the running total equals the target.

Complexity: exponential (O(2^n)) — every subset is tried; fine for small N.
Lesson 3 — Parsing a Nested Structure by Recursion

A value is either a plain number or a parenthesized (left OP right). Evaluate the OUTERMOST operator, then recurse into each side.
```
expression = "42"
print(int(expression))
```
Scroll the code for more ↓
Output
```
42
```
A bare number is the base case — no parentheses, so it is used directly (no recursion needed).

expression = "(6+9)"
inner = expression[1:len(expression) - 1]
split_at = 0
index = 0
while index < len(inner):
    if inner[index] == "+" or inner[index] == "*":
        split_at = index
    index = index + 1
left = int(inner[0:split_at])
right = int(inner[split_at + 1:len(inner)])
if inner[split_at] == "+":
    print(left + right)
else:
    print(left * right)

Output

ONE level: find the operator, split into two numbers, and combine — still no recursion, because each side is a plain number.

data = '((1+2)*(3+4))'
text = data.strip()

def value(expression):
    if expression[0] != "(":
        return int(expression)
    depth = 0
    split_at = -1
    index = 1
    while index < len(expression) - 1:
        character = expression[index]
        if character == "(":
            depth = depth + 1
        elif character == ")":
            depth = depth - 1
        elif depth == 0 and (character == "+" or character == "*"):
            split_at = index
        index = index + 1
    left = value(expression[1:split_at])
    right = value(expression[split_at + 1:len(expression) - 1])
    if expression[split_at] == "+":
        return left + right
    return left * right

print(str(value(text)))

Output

Now each side can ITSELF be a parenthesized expression, so value calls itself on each side — recursion handles arbitrary nesting.
Put it together: the program reads a fully-parenthesized expression from stdin and prints its value.

Try it

import sys

data = sys.stdin.read()
text = data.strip()

def value(expression):
    if expression[0] != "(":
        return int(expression)
    depth = 0
    split_at = -1
    index = 1
    while index < len(expression) - 1:
        character = expression[index]
        if character == "(":
            depth = depth + 1
        elif character == ")":
            depth = depth - 1
        elif depth == 0 and (character == "+" or character == "*"):
            split_at = index
        index = index + 1
    left = value(expression[1:split_at])
    right = value(expression[split_at + 1:len(expression) - 1])
    if expression[split_at] == "+":
        return left + right
    return left * right

print(str(value(text)))

Run the full solver from this unit folder:
```
python assets/l3.py < assets/l3/1.in
```
value(expr) returns a bare number directly, else splits at the top-level (depth-0) operator and recurses on each side.

Complexity: O(len^2) worst case — a scan per recursion level.
A Backtracking Checklist

(1) Name the base case that stops recursion; (2) at each step try each allowed choice; (3) recurse on the smaller problem; (4) UNDO the choice (restore used, or just recurse with a fresh path + [value]) before trying the next. No .pop needed.
- A recursive function solves a smaller copy of the problem; the base case stops the recursion.
- Answers build up as the call stack unwinds, as in recursive_sum and countdown.
- Include-or-skip recursion tries every subset; used[i] = True before recursing and = False after undoes a choice.
- Starting each pick at next_index builds combinations without repeats.
- To evaluate (left OP right), split at the operator at depth zero and evaluate each side the same way.
You can now count or build every possibility with recursion and backtracking.

Unit 9 — Recursion & Backtracking

Lesson 1 — A Function Solving a Smaller Copy

Lesson 2 — Try, Recurse, Undo (Backtracking)

Lesson 3 — Parsing a Nested Structure by Recursion

A Backtracking Checklist