Learning objectives
By the end you can:
- Decompose a problem into precise, orderable steps before writing any code, and trace a short algorithm by hand (on paper, one step at a time) before trusting a program's output.
- Write and read recursive functions: identify the base case and the recursive case in any recursive function, and explain precisely why omitting either produces either an immediately wrong answer or unbounded recursion.
- Trace a recursive call by hand as a call stack (a stack of paused, waiting calls) and predict, before running the code, the exact order in which those calls complete and return.
- State and derive Big-O time complexity: recognizing and deriving O(1), O(log n), O(n), O(n log n), O(n²), and exponential growth from a piece of code by counting operations as a function of input size
n, not by guessing from how the code "feels." - Recognize space complexity, especially a recursive function's call-stack depth, as real memory cost, and predict when a correct recursive definition will crash on realistic input (
RecursionError) long before it produces a wrong answer. - Diagnose and fix the classic recursion/Big-O bugs: a missing or unreachable base case, a hidden O(n) operation buried inside a loop that silently turns O(n) into O(n²), and the mutable-default-argument bug that corrupts naive memoization.
- Reduce a naive O(n²) nested-loop solution to a faster one (an O(n) single pass, or an O(n log n) sort-based approach) by naming precisely which redundant work the nested loop repeats.
- Profile Python code empirically: time it as input size grows, and connect the observed growth curve back to the theoretical Big-O class, understanding that Big-O and wall-clock time are related but different questions, answered by different kinds of evidence.
- Dissect at least one India (₹) and one US ($) finance-flavored problem end to end: state its Big-O, implement both a correct and, where relevant, a faster version, and verify both against hidden tests that defeat a hardcoded answer.
- (Productivity objective: R10 duality.) Use an AI coding copilot to accelerate writing and reviewing recursion- and complexity-sensitive code, without skipping the by-hand understanding step, and verify its output exactly as you verify your own: trace it, run the tests, and confirm it is not calling something that does not exist.
The duality, stated once (R10). Objectives 1–9 are the understanding objective the mastery gate rewards: you pass by demonstrating, closed-book, that you can derive complexity and trace recursion yourself. Objective 10 is the productivity payoff you keep afterward: once you can do the by-hand version, a copilot legitimately makes you faster at the mechanical parts. A tool can draft a recursive function for you; it cannot install the judgment to know whether that function terminates on every input, and that judgment is the entire content of this module.
Prerequisites & connections
Builds on. This is the fourth node of the quant-cs branch, and it assumes real comfort with CS1.01 (Python I, values, variables, control flow, functions, I/O) and CS1.02 (Python II, data structures, pure functions, idiomatic Python): you should already be fluent writing, calling, and returning from functions, and comfortable with lists, dicts, and basic control flow, because recursion is functions calling functions and you cannot reason about a call stack you cannot yet read. CS1.03 (how computers really work) is a close and recent neighbor: its treatment of the stack as literal, finite memory is exactly what turns "the call stack" from a metaphor in this module into a mechanical fact you already believe, and its Python memory experiments (id, sys.getsizeof) are the same instinct (inspect the machine, don't guess) that this module applies to time and space cost instead of memory layout. Per R11 (the branch's day-one-entry rule), the very first node of this branch, CS1.01, unlocks with no finance-phase prerequisite at all; within the branch, however, the chain is sequential, and CS1.04 assumes CS1.01–CS1.03 are done.