Hands-on lab — Day 62: Recursion

#!/usr/bin/env python3
"""recursion.py — worked examples of recursion, as a small CLI.

Every subcommand demonstrates one recursive function so you can watch the
base case and the recursive case do their work on real input:

    factorial  n! by recursion (the "hello world" of recursion)
    sum        add a flat list of numbers by recursion
    flatten    turn an arbitrarily nested list into one flat list
    treesum    add every number in a nested dict/list (a tree walk)
    fib        Fibonacci — naive recursion vs an lru_cache-memoized version,
               reporting call counts so the exponential blow-up is visible

Input comes entirely from command-line arguments (never an interactive
prompt), so the tool can be tested and automated without a human. The nested
data for `flatten` and `treesum` is passed as JSON, which maps cleanly onto
Python lists and dicts.

    python3 recursion.py factorial --n 5
    python3 recursion.py sum --values 1,2,3,4,5
    python3 recursion.py flatten --data "[1, [2, [3, 4]], 5]"
    python3 recursion.py treesum --data '{"a": 1, "b": {"c": 2, "d": [3, 4]}}'
    python3 recursion.py fib --n 30
"""
import argparse
import json
import sys
from functools import lru_cache


def factorial(n):
    """Return n! by recursion.

    Base case: 0! and 1! are 1. Recursive case: n! = n * (n - 1)!. Each call
    shrinks n toward the base case, so the recursion is guaranteed to stop.
    """
    if n < 0:
        raise ValueError("factorial is undefined for negative numbers")
    if n <= 1:                      # base case — stop here, no further calls
        return 1
    return n * factorial(n - 1)     # recursive case — a smaller subproblem


def list_sum(numbers):
    """Return the sum of a flat list by recursion.

    Base case: the empty list sums to 0. Recursive case: the sum is the first
    element plus the sum of the rest. Each call works on a shorter list.
    """
    if not numbers:                 # base case — nothing left to add
        return 0
    return numbers[0] + list_sum(numbers[1:])   # recursive case


def flatten(items):
    """Return a single flat list from an arbitrarily nested list.

    This is a problem recursion suits perfectly: the structure is nested to
    an unknown depth, and the function calls itself on each sublist until it
    reaches plain (non-list) values, which are the base case.
    """
    result = []
    for item in items:
        if isinstance(item, list):
            result.extend(flatten(item))   # recursive case — dive into the sublist
        else:
            result.append(item)            # base case — a leaf value
    return result


def tree_sum(node):
    """Add every number reachable inside a nested dict/list tree.

    A node is a number (a leaf), a list, or a dict. Numbers are the base
    case; lists and dicts are the recursive case — sum the results of walking
    each child. Anything else (strings, None) contributes 0.
    """
    if isinstance(node, bool):
        return 0                                  # bool is a subclass of int; ignore
    if isinstance(node, (int, float)):
        return node                               # base case — a numeric leaf
    if isinstance(node, list):
        return sum(tree_sum(child) for child in node)          # recurse over items
    if isinstance(node, dict):
        return sum(tree_sum(value) for value in node.values())  # recurse over values
    return 0                                      # strings, None, etc.


def fib_naive(n, counter):
    """Return the nth Fibonacci number by naive tree recursion.

    counter is a one-element list used to count how many times this function
    is called, so we can measure the exponential explosion. Each call spawns
    two more (for n >= 2), which is why naive Fibonacci is so wasteful.
    """
    counter[0] += 1
    if n < 2:                       # base cases: fib(0) = 0, fib(1) = 1
        return n
    return fib_naive(n - 1, counter) + fib_naive(n - 2, counter)


def make_memoized_fib():
    """Return an lru_cache-memoized Fibonacci function.

    lru_cache remembers each fib(n) the first time it is computed, so every
    later request for the same n is a cache hit instead of a re-computation.
    That turns the exponential tree into a linear number of computations.
    """
    @lru_cache(maxsize=None)
    def fib(n):
        if n < 2:
            return n
        return fib(n - 1) + fib(n - 2)
    return fib


def cmd_factorial(args):
    """factorial: print n! computed by recursion."""
    result = factorial(args.n)
    print(f"factorial({args.n}) = {result}")
    return 0


def cmd_sum(args):
    """sum: parse a comma-separated list of ints and add it by recursion."""
    text = args.values.strip()
    if not text:
        numbers = []
    else:
        try:
            numbers = [int(piece) for piece in text.split(",")]
        except ValueError:
            raise ValueError(f"--values must be comma-separated integers, got {args.values!r}")
    print(f"sum({numbers}) = {list_sum(numbers)}")
    return 0


def _load_json(text, expect):
    """Parse text as JSON and confirm its top-level type, or raise ValueError."""
    try:
        data = json.loads(text)
    except json.JSONDecodeError as err:
        raise ValueError(f"--data is not valid JSON ({err})")
    if expect == "list" and not isinstance(data, list):
        raise ValueError("--data must be a JSON list, e.g. [1, [2, 3]]")
    if expect == "tree" and not isinstance(data, (list, dict)):
        raise ValueError("--data must be a JSON object or list")
    return data


def cmd_flatten(args):
    """flatten: parse a nested JSON list and print it flattened by recursion."""
    nested = _load_json(args.data, expect="list")
    print(f"flatten -> {flatten(nested)}")
    return 0


def cmd_treesum(args):
    """treesum: parse a nested JSON tree and print the sum of its numbers."""
    tree = _load_json(args.data, expect="tree")
    print(f"treesum -> {tree_sum(tree)}")
    return 0


def cmd_fib(args):
    """fib: compute fib(n) two ways and report the call counts.

    The naive version counts every call; the memoized version reports its
    cache statistics. The contrast is the whole point: memoization collapses
    an exponential number of calls into a linear number of computations.
    """
    n = args.n
    counter = [0]
    naive_value = fib_naive(n, counter)
    naive_calls = counter[0]

    fib = make_memoized_fib()
    memo_value = fib(n)
    info = fib.cache_info()

    assert naive_value == memo_value, "the two methods must agree"
    print(f"fib({n}) = {memo_value}")
    print(f"naive recursion: {naive_calls} calls")
    print(f"memoized (lru_cache): {info.misses} computations, {info.hits} cache hits")
    ratio = naive_calls // max(info.misses, 1)
    print(f"the naive version made {ratio}x more calls than the memoized version computed")
    return 0


def build_parser():
    """Build the argparse parser: five subcommands, one per recursive idea."""
    parser = argparse.ArgumentParser(
        prog="recursion.py",
        description="Worked examples of recursion: factorial, sum, flatten, treesum, fib.",
    )
    subparsers = parser.add_subparsers(
        dest="command",
        required=True,
        metavar="{factorial,sum,flatten,treesum,fib}",
    )

    fac = subparsers.add_parser("factorial", help="compute n! by recursion")
    fac.add_argument("--n", type=int, required=True, help="a non-negative integer")
    fac.set_defaults(func=cmd_factorial)

    add = subparsers.add_parser("sum", help="add a comma-separated list by recursion")
    add.add_argument("--values", required=True, help="e.g. 1,2,3,4")
    add.set_defaults(func=cmd_sum)

    flat = subparsers.add_parser("flatten", help="flatten a nested JSON list")
    flat.add_argument("--data", required=True, help='e.g. "[1, [2, [3, 4]], 5]"')
    flat.set_defaults(func=cmd_flatten)

    tree = subparsers.add_parser("treesum", help="sum every number in a nested JSON tree")
    tree.add_argument("--data", required=True, help='e.g. \'{"a": 1, "b": [2, 3]}\'')
    tree.set_defaults(func=cmd_treesum)

    fib = subparsers.add_parser("fib", help="Fibonacci: naive vs lru_cache memoized")
    fib.add_argument("--n", type=int, required=True, help="which Fibonacci number")
    fib.set_defaults(func=cmd_fib)

    return parser


def main(argv):
    """Entry point: parse arguments, dispatch, and turn a ValueError into
    a clear message plus exit code 1."""
    parser = build_parser()
    args = parser.parse_args(argv[1:])
    try:
        return args.func(args)
    except ValueError as err:
        print(f"error: {err}", file=sys.stderr)
        return 1
    except RecursionError:
        print(
            "error: maximum recursion depth exceeded — the input is too deeply "
            "nested for the default limit (see sys.setrecursionlimit)",
            file=sys.stderr,
        )
        return 1


if __name__ == "__main__":
    sys.exit(main(sys.argv))

lesson_id: D062
day: 62
kind: python-program
languages: [python]
setup_commands:
  - cd labs/sections/programming-with-python/day-062-recursion
  - python3 --version
run_commands:
  - 'python3 examples/recursion.py factorial --n 5'
  - 'python3 examples/recursion.py sum --values 1,2,3,4,5'
  - 'python3 examples/recursion.py flatten --data "[1, [2, [3, 4]], 5]"'
  - 'python3 examples/recursion.py treesum --data ''{"a": 1, "b": [2, 3]}'''
  - 'python3 examples/recursion.py fib --n 30'
test_commands:
  - bash tests/run_tests.sh
cleanup_commands:
  - 'git checkout -- starter/recursion.py  # optional: reset your work'
requires_network: false
requires_api_key: false
estimated_minutes: 30
last_executed: '2026-07-13'
executed_on: 'macOS (Apple Silicon), Python 3.14.0, bash tests/run_tests.sh -> 20 checks, 0 failure(s), exit 0'

# Dependencies — Day 062 lab

**Python 3 only. No third-party packages.**

- `python3` (3.8 or newer; tested on 3.14.0). Preinstalled on most Linux
  distributions and installable on macOS; you set this up on Day 43.
- `bash` for the test runner (preinstalled on macOS and Linux).
- Only the Python standard library is used — specifically `functools`
  (`lru_cache`), `argparse`, `json`, and `sys`, all of which ship with
  Python. There is deliberately no `requirements.txt`: a recursion exercise
  this size should run on a plain Python install with nothing to download
  first.

Check your Python is present and new enough:

```bash
python3 --version
```

If that prints `Python 3.8` or higher, you are ready. Windows users: run the
commands inside WSL, or use `python` in place of `python3` if that is how
Python is exposed on your system. The code is pure standard-library Python
and behaves identically everywhere.

#!/usr/bin/env python3
"""recursion.py — YOUR working file.

Build these recursive functions one exercise at a time. Each numbered
exercise names exactly what to write, including the base case and the
recursive case. The finished reference is in examples/recursion.py — try each
exercise yourself before peeking.

When all five exercises are done, this file behaves like the reference:

    python3 starter/recursion.py factorial --n 5
    python3 starter/recursion.py sum --values 1,2,3,4,5
    python3 starter/recursion.py flatten --data "[1, [2, [3, 4]], 5]"
    python3 starter/recursion.py treesum --data '{"a": 1, "b": [2, 3]}'
    python3 starter/recursion.py fib --n 30

Then run:  bash tests/run_tests.sh
"""
import argparse
import json
import sys
from functools import lru_cache


def factorial(n):
    """Return n! by recursion."""
    # Exercise 1: FACTORIAL.
    # 1. If n < 0, raise ValueError("factorial is undefined for negative numbers").
    # 2. BASE CASE: if n <= 1, return 1 (0! and 1! are both 1). This stops
    #    the recursion — without it the calls never end.
    # 3. RECURSIVE CASE: return n * factorial(n - 1). Each call shrinks n
    #    toward the base case.
    raise NotImplementedError("Exercise 1: implement factorial")


def list_sum(numbers):
    """Return the sum of a flat list by recursion."""
    # Exercise 2: RECURSIVE LIST SUM.
    # 1. BASE CASE: an empty list sums to 0 — `if not numbers: return 0`.
    # 2. RECURSIVE CASE: return numbers[0] + list_sum(numbers[1:]).
    #    Each call works on a shorter list (the "rest").
    raise NotImplementedError("Exercise 2: implement list_sum")


def flatten(items):
    """Return a single flat list from an arbitrarily nested list."""
    # Exercise 3: FLATTEN A NESTED LIST.
    # 1. Make an empty result list.
    # 2. For each item: if it is a list (isinstance(item, list)), it is the
    #    RECURSIVE CASE — extend result with flatten(item). Otherwise it is a
    #    leaf (the BASE CASE) — append it.
    # 3. Return result.
    raise NotImplementedError("Exercise 3: implement flatten")


def tree_sum(node):
    """Add every number reachable inside a nested dict/list tree."""
    # Exercise 4: WALK A NESTED TREE.
    # A node is a number (leaf), a list, or a dict. Handle each:
    # 1. `if isinstance(node, bool): return 0`  (bool is a subclass of int)
    # 2. BASE CASE: `if isinstance(node, (int, float)): return node`
    # 3. RECURSIVE CASE (list): return sum(tree_sum(child) for child in node)
    # 4. RECURSIVE CASE (dict): return sum(tree_sum(v) for v in node.values())
    # 5. Anything else (strings, None): return 0
    raise NotImplementedError("Exercise 4: implement tree_sum")


def fib_naive(n, counter):
    """Return fib(n) by naive tree recursion, counting every call."""
    # Exercise 5: NAIVE FIBONACCI (tree recursion).
    # 1. Increment the call counter: counter[0] += 1  (already written below;
    #    keep it first so every call is counted).
    # 2. BASE CASES: if n < 2, return n  (fib(0) = 0, fib(1) = 1).
    # 3. RECURSIVE CASE: return fib_naive(n - 1, counter) + fib_naive(n - 2, counter).
    #    Notice each call makes TWO more — that is why this is exponential.
    counter[0] += 1
    raise NotImplementedError("Exercise 5: implement fib_naive")


def make_memoized_fib():
    """Return an lru_cache-memoized Fibonacci function. (Provided.)

    lru_cache remembers each fib(n) the first time it is computed, so later
    requests for the same n are cache hits instead of re-computations. That
    turns the exponential tree into a linear number of computations.
    """
    @lru_cache(maxsize=None)
    def fib(n):
        if n < 2:
            return n
        return fib(n - 1) + fib(n - 2)
    return fib


def cmd_factorial(args):
    """factorial: print n! computed by recursion. (Provided.)"""
    print(f"factorial({args.n}) = {factorial(args.n)}")
    return 0


def cmd_sum(args):
    """sum: parse a comma-separated list and add it by recursion. (Provided.)"""
    text = args.values.strip()
    if not text:
        numbers = []
    else:
        try:
            numbers = [int(piece) for piece in text.split(",")]
        except ValueError:
            raise ValueError(f"--values must be comma-separated integers, got {args.values!r}")
    print(f"sum({numbers}) = {list_sum(numbers)}")
    return 0


def _load_json(text, expect):
    """Parse text as JSON and confirm its top-level type. (Provided.)"""
    try:
        data = json.loads(text)
    except json.JSONDecodeError as err:
        raise ValueError(f"--data is not valid JSON ({err})")
    if expect == "list" and not isinstance(data, list):
        raise ValueError("--data must be a JSON list, e.g. [1, [2, 3]]")
    if expect == "tree" and not isinstance(data, (list, dict)):
        raise ValueError("--data must be a JSON object or list")
    return data


def cmd_flatten(args):
    """flatten: parse a nested JSON list and print it flattened. (Provided.)"""
    print(f"flatten -> {flatten(_load_json(args.data, expect='list'))}")
    return 0


def cmd_treesum(args):
    """treesum: parse a nested JSON tree and print the sum of its numbers. (Provided.)"""
    print(f"treesum -> {tree_sum(_load_json(args.data, expect='tree'))}")
    return 0


def cmd_fib(args):
    """fib: compute fib(n) two ways and report the call counts. (Provided.)"""
    n = args.n
    counter = [0]
    naive_value = fib_naive(n, counter)
    naive_calls = counter[0]

    fib = make_memoized_fib()
    memo_value = fib(n)
    info = fib.cache_info()

    assert naive_value == memo_value, "the two methods must agree"
    print(f"fib({n}) = {memo_value}")
    print(f"naive recursion: {naive_calls} calls")
    print(f"memoized (lru_cache): {info.misses} computations, {info.hits} cache hits")
    ratio = naive_calls // max(info.misses, 1)
    print(f"the naive version made {ratio}x more calls than the memoized version computed")
    return 0


def build_parser():
    """Build the argparse parser: five subcommands, one per idea. (Provided.)"""
    parser = argparse.ArgumentParser(
        prog="recursion.py",
        description="Worked examples of recursion: factorial, sum, flatten, treesum, fib.",
    )
    subparsers = parser.add_subparsers(
        dest="command",
        required=True,
        metavar="{factorial,sum,flatten,treesum,fib}",
    )

    fac = subparsers.add_parser("factorial", help="compute n! by recursion")
    fac.add_argument("--n", type=int, required=True, help="a non-negative integer")
    fac.set_defaults(func=cmd_factorial)

    add = subparsers.add_parser("sum", help="add a comma-separated list by recursion")
    add.add_argument("--values", required=True, help="e.g. 1,2,3,4")
    add.set_defaults(func=cmd_sum)

    flat = subparsers.add_parser("flatten", help="flatten a nested JSON list")
    flat.add_argument("--data", required=True, help='e.g. "[1, [2, [3, 4]], 5]"')
    flat.set_defaults(func=cmd_flatten)

    tree = subparsers.add_parser("treesum", help="sum every number in a nested JSON tree")
    tree.add_argument("--data", required=True, help='e.g. \'{"a": 1, "b": [2, 3]}\'')
    tree.set_defaults(func=cmd_treesum)

    fib = subparsers.add_parser("fib", help="Fibonacci: naive vs lru_cache memoized")
    fib.add_argument("--n", type=int, required=True, help="which Fibonacci number")
    fib.set_defaults(func=cmd_fib)

    return parser


def main(argv):
    """Entry point: parse arguments, dispatch, and turn errors into exit 1. (Provided.)"""
    parser = build_parser()
    args = parser.parse_args(argv[1:])
    try:
        return args.func(args)
    except ValueError as err:
        print(f"error: {err}", file=sys.stderr)
        return 1
    except RecursionError:
        print(
            "error: maximum recursion depth exceeded — the input is too deeply "
            "nested for the default limit (see sys.setrecursionlimit)",
            file=sys.stderr,
        )
        return 1


if __name__ == "__main__":
    sys.exit(main(sys.argv))

# Recursion design worksheet

Fill this in *before* writing code for the practice assignment. The whole
skill of recursion is naming the **base case** and the **recursive case**
before you touch the keyboard — this worksheet forces exactly that. One row
per function you design.

## The problem

- **What are you computing (one sentence):**
- **What is the input, and how is it "smaller" on each call:**
- **What does a single, plain (non-recursive) piece of the input look like:**

## Base case and recursive case

For each recursive function you write, fill one row.

| Function | Base case (when to STOP, and what to return) | Recursive case (the smaller subproblem, and how you combine it) |
| -------- | -------------------------------------------- | --------------------------------------------------------------- |
|          |                                              |                                                                 |
|          |                                              |                                                                 |

## Termination check

For each function, answer: **why is every recursive call guaranteed to move
closer to the base case?** (If you cannot answer this, the function may recurse
forever and hit `RecursionError`.)

1.
2.

## Recursion vs iteration

For each function, would a plain loop be simpler or clearer? Say which you
chose and why. (Recursion shines for tree/nested-structure problems; a loop
is often better for a flat sequence.)

-
-

## Recorded behaviour (fill in after you build it)

- One good run (command and its output):
- One rejected/edge run (command, message, and `echo $?`):
- If you wrote a Fibonacci-style function twice (naive and memoized), the two
  call counts you measured:

#!/usr/bin/env bash
# Tests for the Day 062 lab. Run from the lab directory:
#   bash tests/run_tests.sh
#
# Exercises the complete reference module (examples/recursion.py) across all
# five recursive subcommands: factorial (incl. the base case and a rejected
# negative), recursive list sum (incl. the empty-list base case), flatten of
# a nested list, treesum over a nested dict/list tree, and fib (naive vs
# memoized). Every check verifies BOTH the printed output and the exit code.
# It then imports the pure functions to check return values, and — the key
# recursion assertion — imports fib_naive and the memoized fib and asserts
# the naive version makes FAR MORE calls than the memoized version computes
# (a call-count comparison, not a fragile wall-clock timing). Finally it
# checks the learner's starter — structurally while exercises are unfinished,
# and to the same strict standard once they are complete. No network,
# non-interactive. Exits 0 only if every check passes.
set -u

# Keep the working tree clean: do not let imported modules write __pycache__.
export PYTHONDONTWRITEBYTECODE=1

lab_dir="$(cd "$(dirname "${BASH_SOURCE[0]}")/.." && pwd)"
ref="${lab_dir}/examples/recursion.py"
starter="${lab_dir}/starter/recursion.py"
failures=0
checks=0

check() {
  local label="$1" ok="$2"
  checks=$((checks + 1))
  if [ "${ok}" = "yes" ]; then
    echo "  ok: ${label}"
  else
    echo "  FAIL: ${label}"
    failures=$((failures + 1))
  fi
}

# check_run <label> <script> <expect_exit> <needle> <arg...>
# Runs the module and checks the exit code and that combined output contains
# the needle.
check_run() {
  local label="$1" script="$2" expect_exit="$3" needle="$4"
  shift 4
  local out code
  out="$(python3 "${script}" "$@" 2>&1)"
  code=$?
  if [ "${code}" -eq "${expect_exit}" ] && printf '%s' "${out}" | grep -qF "${needle}"; then
    check "${label}" "yes"
  else
    check "${label}" "no"
    echo "    (exit ${code}, expected ${expect_exit}; output: ${out})"
  fi
}

run_cli_checks() {
  local script="$1"
  echo "Testing ${script} ..."
  # factorial: recursive case and the base case, plus a rejected negative.
  check_run "factorial 5 = 120"          "${script}" 0 "factorial(5) = 120"   factorial --n 5
  check_run "factorial 0 = 1 (base case)" "${script}" 0 "factorial(0) = 1"    factorial --n 0
  check_run "factorial negative rejected" "${script}" 1 "undefined for negative" factorial --n -3
  # recursive list sum, incl. the empty-list base case.
  check_run "sum 1..5 = 15"              "${script}" 0 "= 15"                 sum --values 1,2,3,4,5
  check_run "sum empty = 0 (base case)"  "${script}" 0 "sum([]) = 0"          sum --values ""
  check_run "sum bad values rejected"    "${script}" 1 "comma-separated integers" sum --values 1,x,3
  # flatten a nested list to any depth.
  check_run "flatten nested list"        "${script}" 0 "flatten -> [1, 2, 3, 4, 5]" flatten --data "[1, [2, [3, 4]], 5]"
  check_run "flatten rejects bad JSON"   "${script}" 1 "not valid JSON"       flatten --data "[1, 2"
  # treesum walks a nested dict/list tree.
  check_run "treesum nested tree = 10"   "${script}" 0 "treesum -> 10"        treesum --data '{"a": 1, "b": {"c": 2, "d": [3, 4]}}'
  # fib: value, naive call count, and that memoized computes fewer.
  check_run "fib 10 value = 55"          "${script}" 0 "fib(10) = 55"         fib --n 10
  check_run "fib 10 naive = 177 calls"   "${script}" 0 "naive recursion: 177 calls" fib --n 10
  check_run "fib 10 memoized 11 computations" "${script}" 0 "memoized (lru_cache): 11 computations" fib --n 10
}

# --- Reference module: always tested strictly ---
run_cli_checks "${ref}"

# --- Import pure functions and check return values (importability payoff) ---
echo "Testing importability of examples/recursion.py ..."
if python3 -c "import sys; sys.path.insert(0, '${lab_dir}/examples'); \
from recursion import factorial; \
assert factorial(0) == 1; assert factorial(5) == 120"; then
  check "import factorial computes 1 and 120" "yes"
else
  check "import factorial computes 1 and 120" "no"
fi
if python3 -c "import sys; sys.path.insert(0, '${lab_dir}/examples'); \
from recursion import list_sum; \
assert list_sum([]) == 0; assert list_sum([1, 2, 3, 4, 5]) == 15"; then
  check "import list_sum computes 0 and 15" "yes"
else
  check "import list_sum computes 0 and 15" "no"
fi
if python3 -c "import sys; sys.path.insert(0, '${lab_dir}/examples'); \
from recursion import flatten; \
assert flatten([1, [2, [3, 4]], 5]) == [1, 2, 3, 4, 5]"; then
  check "import flatten handles deep nesting" "yes"
else
  check "import flatten handles deep nesting" "no"
fi
if python3 -c "import sys; sys.path.insert(0, '${lab_dir}/examples'); \
from recursion import tree_sum; \
assert tree_sum({'a': 1, 'b': {'c': 2, 'd': [3, 4]}}) == 10; \
assert tree_sum({'x': 'skip', 'y': True, 'z': 5}) == 5"; then
  check "import tree_sum walks a tree and ignores non-numbers" "yes"
else
  check "import tree_sum walks a tree and ignores non-numbers" "no"
fi

# --- The key recursion assertion: memoization slashes the call count ---
# Robust: compares CALL COUNTS (naive calls vs memoized computations), never
# wall-clock time, so it is deterministic on every machine.
echo "Testing that memoization slashes the call count (examples/recursion.py) ..."
if python3 -c "import sys; sys.path.insert(0, '${lab_dir}/examples'); \
from recursion import fib_naive, make_memoized_fib; \
c = [0]; v1 = fib_naive(25, c); naive = c[0]; \
fib = make_memoized_fib(); v2 = fib(25); misses = fib.cache_info().misses; \
assert v1 == v2 == 75025, ('values', v1, v2); \
assert misses == 26, ('unique computations', misses); \
assert naive > 50 * misses, ('naive should dwarf memoized', naive, misses)"; then
  check "memoized fib(25) computes 26 vs naive's 242785 calls" "yes"
else
  check "memoized fib(25) computes 26 vs naive's 242785 calls" "no"
fi

# --- Learner starter ---
echo "Testing starter/recursion.py ..."
if python3 -c "compile(open('${starter}').read(), '${starter}', 'exec')" 2>/dev/null; then
  check "starter is valid Python" "yes"
else
  check "starter is valid Python" "no"
fi

if grep -q 'NotImplementedError' "${starter}"; then
  echo "Note: starter/recursion.py still has unfinished exercises — testing structure only."
  grep -q 'def factorial' "${starter}" && check "starter defines factorial" "yes" || check "starter defines factorial" "no"
  grep -q 'def fib_naive' "${starter}" && check "starter defines fib_naive" "yes" || check "starter defines fib_naive" "no"
else
  run_cli_checks "${starter}"
  grep -q '__name__ == "__main__"' "${starter}" && check "starter has the main guard" "yes" || check "starter has the main guard" "no"
fi

echo
echo "${checks} checks, ${failures} failure(s)."
[ "${failures}" -eq 0 ]