Back to path
BeginnerLexi · Project 4 of 12 ~6h· 5 milestones

Walk it recursively and mind the stack

Continues from the last build: A searchable index with fast exact lookups and sorted-range search, but no way to group results by the folders they actually live in.

Rung 3 gave you a sorted list and binary search, so you can find a title or a range of titles in O(log n) instead of scanning everything.

recursion (base case + recursive case)call stack reasoningdivide and conquermerge sortk-way merge of sorted listsRecursionError diagnosisexplicit stack (iterative traversal)benchmarking with growing n
Build this freeBrowse all projectsNo credit card. Already a member?

What you'll build

A recursive folder indexer with a correct base case and recursive case, a merge sort and a recursive k-way postings merge that avoids rebuilding sorted results from scratch, a traced understanding of the call stack and Python's recursion limit, and an explicit-stack rewrite proven by a growing-n benchmark (n, 10n, 100n) that shows recursion failing and the stack version surviving.

See how we teach, before you sign up

You don't just get code dumped on you. Every starter file and every solution is explained line-by-line, in plain English. Here's one real file from this project:

lexi/index.pypy
from __future__ import annotations
from bisect import bisect_left


class SortedIndex:
    """Carried from Rung 3: a flat sorted list of (title, doc_id) pairs."""

    def __init__(self, titles: list[str]) -> None:
        self.entries = sorted((title.lower(), i) for i, title in enumerate(titles))

    def exact_lookup(self, title: str) -> int | None:
        target = title.lower()
        keys = [t for t, _ in self.entries]
        pos = bisect_left(keys, target)
        if pos < len(keys) and keys[pos] == target:
            return self.entries[pos][1]
        return None

Reading this file

  • class SortedIndex:The Rung 3 structure: one sorted list of (title, doc_id) pairs.
  • def exact_lookup(self, title: str) -> int | None:Binary search from Rung 3, unchanged.
  • pos = bisect_left(keys, target)O(log n) search, the payoff from the last rung.
  • self.entries = sorted((title.lower(), i) for i, title in enumerate(titles))Building this sorted list is where this rung's merge sort will matter once titles come from many folders.
  • return NoneExplicit miss case, the same discipline you need for recursion's base cases.

Carried unchanged from Rung 3. Still used for flat exact-title lookups; this rung adds hierarchical grouping on top.

That's 1 of 9 explained code blocks in this single project.

The build, milestone by milestone

  1. 1

    Walk the folder tree recursively and build the index

    4 guided steps

    Nested folders mean the walk depth is unknown until runtime, a fixed number of nested loops cannot express 'however many levels deep this happens to go'. Recursion mirrors the structure of the data itself: a directory is defined in terms of smaller directories and files, so the function that walks it is naturally defined in terms of itself.

  2. 2

    Trace the call stack before it traces you

    4 guided steps

    To reason about when recursion is fine and when to 'mind the stack' with an explicit one, you need to actually see depth grow with folder nesting, and know Python's default recursion limit (sys.getrecursionlimit(), usually 1000) is a guardrail, not a design target.

  3. 3

    Divide and conquer: sort doc ids with merge sort

    4 guided steps

    Rung 3 searched an already-sorted list; this rung has to PRODUCE sorted, duplicate-free postings after combining many small per-folder lists. Merge sort's split-recurse-merge shape is exactly the shape you reuse in the next milestone to merge sorted postings instead of re-sorting from scratch.

  4. 4

    Merge postings by recursion, not rebuilding

    4 guided steps

    The Milestone 1 build_index used setdefault + extend, which leaves postings unsorted and full of duplicates. A query needs sorted, deduplicated doc-id lists (later rungs intersect postings lists for multi-word queries), so this milestone merges sorted lists on the way up the tree instead of dumping raw lists and sorting once at the very end.

  5. 5

    Swap the recursive walk for an explicit stack on deep trees

    4 guided steps

    Recursion is one implementation of 'walk a tree', not the only one. Anywhere the interpreter uses a call stack, you can trade it for your own stack living on the heap, which has no ~1000-frame ceiling, only available memory.

What's inside when you start

4 starter files, ready to clone
5 guided milestones
5 full reference solutions
9 code blocks explained line-by-line
5 "is it working?" checks
4 interview questions it prepares you for

You'll walk away with

lexi/recursion_walk.py with a working recursive build_index (correct base case + recursive case, in-place merge)
lexi/merge_sort.py with a working merge sort (merge_sort + merge functions)
A merge_postings function that recursively k-way merges sorted postings lists with deduplication
lexi/stack_walk.py with an iterative build_index_iterative using an explicit stack
bench_recursion.py producing timed results for depths n, 10n, 100n showing the RecursionError crossover point
Unit tests covering the recursive walk, merge sort, and merge_postings

This is portfolio-grade. Build it free.

Sign up to unlock every milestone step-by-step, the code skeletons, full reference solutions, and checkable tasks, with your progress saved as you build.

Start building