Intuition The one core ideaA recursive function is a machine that solves a big job by asking a slightly smaller copy of itself to do most of the work, then adding one last touch. To read the parent topic you only need to trust one picture: a chain of boxes that pile down to a tiny obvious answer, then hand results back up .
This page assumes you know nothing . Every symbol on the parent page is unpacked below, in an order where each idea leans only on the ones before it.
Before any symbol, look at the shape of what recursion does.
Intuition Read the figureA tall problem (top) is broken into a smaller version of the same problem (the arrow going down-left ). This repeats until you reach the base case — the smallest box, whose answer needs no more work. Then answers travel back up-right , each box adding its one piece. That down-then-up motion is the whole subject . Keep this image in your head for everything below.
A variable is a labelled box that holds one value. Writing n = 3 means "put the number 3 into the box named n."
The picture: a box with a name-tag n and the number 3 sitting inside.
Why the topic needs it: every recursive function has an input box (usually named n, lo, hi, or target). To follow a trace you must know a name just points at whatever is currently in its box.
= is NOT "equals" in code
Why it feels right: in maths = means "these two sides are the same."
The trap: in Python = means ==assign == — "copy the right side into the box on the left." So n = n - 1 is legal: it reads the box, subtracts 1, stores it back.
The check: the question "are these equal?" uses two equals signs == (see §8).
n n how many things to multiply ; in Fibonacci it is which term we want ; in binary search the "size" is how many list items are still in play .
The picture: the height of the tall box in §0. A "smaller subproblem" simply means a shorter box — n − 1 n /2
Why the topic needs it: recursion only terminates if each call is strictly smaller . If the box never shrinks, you never reach the tiny base box, and the pile grows forever.
Every formula on the parent page is built from just four operations. Here they are, from zero.
+ and subtract -
a + b ::= addition — put two amounts together. 2 + 3 = 5 a - b ::= subtraction — take away. 5 − 1 = 4
The picture: a number line. + steps you right , - steps you left .
Why the topic needs it: n - 1 (subtract) is how factorial and binary search make the problem smaller ; F_{n-1} + F_{n-2} (add) is the whole Fibonacci rule — glue two smaller answers together.
* (written × in maths) and the product
a * b ::= multiplication — repeated addition. 4 × 3 = 4 + 4 + 4 = 12 *; in maths you often see ×.
A product is the result of multiplying several numbers together.
/ and half-ing
a / b ::= division — split into equal parts, or ask "how many bs fit in a?" 6/2 = 3 n /2 n
The catch: / can give a fraction : 5/2 = 2.5 // (see §7).
The parent writes factorial as a chain of multiplications:
n ! = n × ( n − 1 ) × ⋯ × 2 × 1
⋯ ⋯ n − 1 2
empty product = 1
Multiplying nothing at all gives 1 Why 1 and not 0? 1 5 × 1 = 5 0 ! = 1
Why the topic needs it: factorial is a product, and its base case 0 ! = 1
The picture: a staircase of blocks 3 , 2 , 1
Intuition Why the picture makes the recurrence obviousCircle everything below the top block: those blocks are exactly ( n − 1 )! n ! = n × ( n − 1 )!
F n subscript . F n n not F n F 0 F 1
The picture: a row of boxes labelled F 0 , F 1 , F 2 , …
≥ n ≥ 2 n or equal to 2." The line under >
Why the topic needs it: because the rule reaches back two boxes, you need two known starting boxes (F 0 , F 1
Definition List and indexA list is an ordered row of values, e.g. [1,3,5,7,9,11].
An index is the position number of a slot, starting at 0 . So in that list, arr[0] is 1, arr[2] is 5.
Intuition Read the figureThe top row shows the values; the bottom row shows their indices 0,1,2,3,4,5. Notice lo, hi, and mid in binary search are all indices — they point at slots , not values. arr[mid] means "the value living at slot mid."
lo, hi, mid
lo ::= index of the left end of the part of the list still being searched.hi ::= index of the right end still being searched.mid ::= the middle index , computed as (lo + hi) // 2.
Definition Floor division//
// divides (like / from §3) and then throws away any fraction, rounding down to a whole number. (0+5)//2 = 2 (not 2.5), because an index must be a whole slot number.
/ vs //
The trap: plain / from §3 would give (0+5)/2 = 2.5, and you cannot look at "slot 2.5" — there is no half-slot in a list.
The fix: mid = (lo + hi) // 2 rounds down to a real index. Use / for ordinary numbers, // when you need a whole position.
Why the topic needs it: binary search always jumps to the middle slot , and slots are whole numbers — so it uses //, not /.
The picture: a balance scale. arr[mid] < target tips left → the value is too small → the answer must be further right in a sorted list.
= vs ==
The trap: n = 0 puts 0 into n; n == 0 asks whether n is 0. Mixing them is the most common beginner bug.
The fix: one = stores , two == asks .
Why the topic needs it: every base case is a comparison — if n == 0, if lo > hi, if arr[mid] == target. Each one is a question that decides "stop, or recurse smaller."
def, return, call
def name(...) ::= defines a reusable machine named name.call ::= running that machine on specific inputs, e.g. factorial(3).return X ::= "hand back the value X to whoever called me, and stop."
The picture: a vending machine. You put inputs in (3), press go (call), and one value drops out (return). A recursive call is the machine reaching over and pressing its own button with a smaller input.
Why the topic needs it: recursion literally means "a function that calls itself." Without return, the smaller answer never travels back up the chain in §0.
Definition Call stack and stack frameEach time a function is called, the computer makes a stack frame : a box holding that call's own variables and a note saying "where to return." These boxes stack on top of each other, newest on top. A finished call's box is removed (popped ) and its answer flows to the box below.
Intuition Read the figureLeft column: frames pile up as factorial(3) calls factorial(2) calls factorial(1) calls factorial(0) — each waiting, holding a paused multiplication. Right column: once factorial(0) returns 1, boxes unwind upward, each finishing its n * (...). This is the same down-then-up motion as §0, now shown as literal memory.
RecursionError
If the box never shrinks to a base case, frames pile up without limit, memory runs out, and Python stops with RecursionError: maximum recursion depth exceeded. That is what "no base case" looks like physically: an infinite tower.
Why the topic needs it: it explains why the multiplications in factorial wait, then combine bottom-up — the stack is the topic's hidden memory.
Θ ( ⋅ ) Θ ( f ( n )) f in step with f ( n ) shape of the growth. See Big-O Notation for the full story.
log 2 n log 2 n n n = 8 8 → 4 → 2 → 1 log 2 8 = 3
φ φ ≈ 1.618 Θ ( φ n ) multiplies by 1.618 n — explosive, because it re-solves the same little problems again and again.
The picture: log 2 n gently rising curve (halving is fast); φ n rocket (repeated multiplication). Same axis, wildly different climbs.
Why the topic needs it: these three symbols are how the parent's summary table compares factorial (Θ ( n ) Θ ( log n ) Θ ( φ n )
T ( n ) T ( n ) n recurrence writes T ( n ) smaller T
factorial: T ( n ) = T ( n − 1 ) + c
binary search: T ( n ) = T ( n /2 ) + c half the job.
Here c
Why the topic needs it: unrolling these recurrences is how the parent derives Θ ( n ) Θ ( log n ) T own cost recursively — fitting.
The diagram below is a flowchart : each rounded label is one idea from this page, and an arrow → means "you need the idea at the tail before the idea at the head." Read arrows as "feeds into." Follow any path from top to bottom and you are walking the safe learning order: basic symbols on the left/top, the three recursion problems in the middle, the cost language at the bottom.
Add subtract multiply divide
Test yourself — cover the right side and answer each.
What does n = n - 1 actually do? Reads the box n, subtracts 1, and stores the result back into n (assignment, not equality).
What is the difference between = and ==? = stores a value; == asks whether two values are equal (True/False).
What do + and - mean on a number line? + steps right (add amounts together); - steps left (take away).
Why does Fibonacci use +? Each term is the sum of the two before it: F n = F n − 1 + F n − 2
What does n /2 Half of n
Why does 0 ! = 1 It is the empty product — multiplying nothing leaves 1, the value that changes nothing.
What does the subscript in F n The position in the sequence (the n F n
In arr[mid], is mid a value or a position? A position (index); arr[mid] fetches the value living at that slot.
Why use // instead of / for mid? Indices must be whole numbers; // rounds down so you land on a real slot, whereas / could give 2.5.
What is a stack frame? A box holding one call's variables and its return spot; frames pile up then pop.
What causes RecursionError? Calls never reach a base case, so frames pile up forever until memory runs out.
What does log 2 n How many times you can halve n
What does Θ ( f ( n )) The shape of how running time grows with input size, ignoring constants.
What does the recurrence T ( n ) = T ( n /2 ) + c Doing constant work then solving a half-size problem — the pattern behind Θ ( log n )
