Recursion 🔁
The topic where a function straight-up calls itself. Sounds cursed, actually kinda genius. Let him cook. 🧑🍳
🎯 What you'll unlock this lesson
- ✅ Understand the essential features of recursion (no cap, it's simpler than it looks)
- ✅ See how recursion looks in real code
- ✅ Trace recursive algorithms step by step
- ✅ Write your own recursive algorithms
- ✅ Know when recursion is actually the W move
- ✅ Get what the compiler does behind the scenes (stacks + unwinding)
💡 So what even is recursion? 24.01
A function or procedure is a recursive routine if it is defined in terms of itself. Basically it calls a smaller copy of itself until the problem is tiny enough to answer instantly. 🪆
The classic example: factorial ( n! )
0! = 1
Gives an answer directly. The "we can stop now" case. 🛑
n! = n × (n − 1)!
Defined using itself, and must move closer to the base case every call. 📉
Every recursive solution has these two parts. That's the whole vibe. 💅
📏 The 3 Golden Rules of a recursive subroutine
Break rule 3 and your program loops forever = stack overflow. Infinite dream, never wake up. 💀
🃏 Key-term flashcards tap to flip
💻 Coding factorial: two ways 24.02
Same answer, totally different energy. Compare the loop vs the recursion 👇
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER Result <- 1 FOR i <- 1 TO n Result <- Result * i NEXT i RETURN Result ENDFUNCTION
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER IF n = 0 THEN Result <- 1 // base case ELSE Result <- n * Factorial(n - 1) // general case ENDIF RETURN Result ENDFUNCTION
Notice the recursive version basically copy-pastes the maths definition. That's the whole flex of recursion — it's giving elegance. ✨
⬇️ Worked example: counting down 24.02
PROCEDURE CountDownFrom(n : INTEGER) FOR i <- n DOWNTO 0 OUTPUT i NEXT i ENDPROCEDURE
PROCEDURE CountDownFrom(n : INTEGER) OUTPUT n IF n > 0 THEN CALL CountDownFrom(n - 1) ENDIF ENDPROCEDURE
- 🛑 Base case: n reaches 0 — it's output, but no further call is made.
- 🔁 General case: output n, then count down from n − 1.
🗣️ Discussion point
- ❓ What happens if Factorial(0) is called? (Hint: it hits the base case instantly — clean.)
- ⚠️ What about Factorial(-2)? Which rule does it break? (It never reaches 0 → breaks Rule 3.)
- 🛠️ What would you change so the definition holds for all n? (e.g. guard against negatives.)
🔍 Output before or after the call? 24.03
This is the plot twist of the whole chapter. Where you put OUTPUT changes the order completely. 🤯
CountDownFrom(3) — OUTPUT comes before the call → 3 2 1 0
| Call | Procedure call | OUTPUT | n > 0 |
|---|---|---|---|
| 1 | CountDownFrom(3) | 3 | TRUE |
| 2 | CountDownFrom(2) | 2 | TRUE |
| 3 | CountDownFrom(1) | 1 | TRUE |
| 4 | CountDownFrom(0) | 0 | FALSE |
CountUpTo(3) — OUTPUT comes after the call → 0 1 2 3
| Call | Procedure call | n > 0 | OUTPUT |
|---|---|---|---|
| 1 | CountUpTo(3) | TRUE | — |
| 2 | CountUpTo(2) | TRUE | — |
| 3 | CountUpTo(1) | TRUE | — |
| 4 | CountUpTo(0) | FALSE | 0 |
| 4 | CountUpTo(1) returns | — | 1 |
| 3 | CountUpTo(2) returns | — | 2 |
| 2 | CountUpTo(3) returns | — | 3 |
Anything written after the recursive call is frozen until the calls unwind back to that line. Move OUTPUT to the end → order flips. Reverse uno card. 🔄
🧮 Tracing Factorial(4) → 24
| Call | Call made | n = 0 | Result | Return value |
|---|---|---|---|---|
| 1 | Factorial(4) | FALSE | — | — |
| 2 | Factorial(3) | FALSE | — | — |
| 3 | Factorial(2) | FALSE | — | — |
| 4 | Factorial(1) | FALSE | — | — |
| 5 | Factorial(0) | TRUE | 1 | 1 |
| 4 | Factorial(1) returns | — | 1 × 1 | 1 |
| 3 | Factorial(2) returns | — | 2 × 1 | 2 |
| 2 | Factorial(3) returns | — | 3 × 2 | 6 |
| 1 | Factorial(4) returns | — | 4 × 6 | 24 |
The RETURN column is another "after the call" thing — it only fills in as each call finishes and control unwinds back up. ⤴️
🪜 The calls unwinding (diagram)
Down the rabbit hole → hit the base case → bounce results back up. 🐇
PROCEDURE X(n : INTEGER) IF (n = 0) OR (n = 1) THEN OUTPUT n ELSE CALL X(n DIV 2) OUTPUT (n MOD 2) ENDIF ENDPROCEDURE
Trace of X(19): calls go deeper first (X(19)→X(9)→X(4)→X(2)→X(1)), then outputs unwind back up:
Output: 1 0 0 1 1
👀 That's 10011 = binary for 19! This algorithm converts a number to binary. Sneaky W. 🧠
🥞 Running a recursive subroutine 24.04
Recursion only works because the compiler makes object code that uses a stack — pushing return addresses + local variables every time the subroutine calls itself.
010 PROGRAM 030 FUNCTION Factorial(n : INTEGER) RETURNS INTEGER 040 IF n = 0 THEN 060 Result <- 1 070 ELSE 080 Result <- n * Factorial(n - 1) 090 ENDIF 100 RETURN Result 110 ENDFUNCTION 150 DECLARE Answer : INTEGER 160 Answer <- Factorial(3) 170 OUTPUT Answer 190 ENDPROGRAM
Line 160 calls Factorial(3) → pushes a frame. Line 80 calls again for each smaller n → another frame each time — until n = 0 (base case). 📚
🎮 Interactive Call-Stack Visualizer signature move
Pick an n, hit Step (or Auto-run) and watch frames get pushed going deeper, then popped as they unwind. This IS the "we need to go deeper" meme, live. 👇
📚 Stack contents during Factorial(3)
| Step | Description | Stack (top frame) |
|---|---|---|
| 1 | 1st call made | n = 3 · return to line 160 |
| 2 | 2nd call made | n = 2 · return to line 80 (n=3) |
| 3 | 3rd call made | n = 1 · return to line 80 (n=2) |
| 4 | 4th call — base case! 🛑 | n = 0 · return to line 80 (n=1) |
| 5 | Result 1 pushed, return to call 3 | pop n=0 → Result 1 |
| 6 | New Result 1×1, return to call 2 | pop n=1 → Result 1 |
| 7 | New Result 2×1, return to call 1 | pop n=2 → Result 2 |
| 8 | New Result 3×2, return to main | pop n=3 → Result 6 🎉 |
Every call pushes a frame. Base case reached → each return pops a frame, uses that result to compute the next, until we're back at line 160 with the final answer 6. 🥳
🎬 Meme of the lesson
Recursion = the "we need to go deeper" meme. 🌀
Each recursive call is a dream within a dream — Factorial(4) calls Factorial(3), calls Factorial(2)... one level deeper each time. Nobody wakes up until someone hits the base case, Factorial(0). Then everyone wakes up in reverse order, level by level, each handing their result up to the dream that called them.
That reverse wake-up sequence? That's literally unwinding the stack. 🧠💥
⚖️ Benefits vs Drawbacks 24.05
✅ Benefits (W's)
- ✨ Often more elegant & shorter than a loop, especially for naturally-recursive problems.
- ⚙️ Some optimising compilers convert recursion into iteration when making object code.
⚠️ Drawbacks (L's)
- 🐘 Repeated calls eat memory + processor time — each call needs its own stack frame.
- 💥 CountDownFrom(100) needs 100 stack frames before it finishes.
🧠 Mini-quiz — no cap, prove it
📝 Exam-style questions try, then peek
- 🔁 Iteration repeats using a loop; recursion repeats by the routine calling itself, needing a base + general case.
- ✅ Advantage: shorter/more elegant for naturally recursive problems.
- ⚠️ Disadvantage: heavy memory/processor use — one stack frame per call.
- 📖 "Recursively defined" = defined in terms of itself (Power calls Power with a smaller exponent).
- 🧮 Trace Power(2, 4): 2×2×2×2×1 = 16 (base case Power(2,0)=1, then unwinds ×2 each time).
- 🥞 The stack stores each call's return address + locals, then pops them as results unwind.
// Non-recursive version FUNCTION Power(Base, Exponent : INTEGER) RETURNS INTEGER Result <- 1 FOR i <- 1 TO Exponent Result <- Result * Base NEXT i RETURN Result ENDFUNCTION
- 🛑 Base cases: Fibonacci(0) = 0 and Fibonacci(1) = 1.
- 🔁 General case: Fibonacci(n) = Fibonacci(n − 1) + Fibonacci(n − 2).
- 🧮 Fibonacci(4) = Fib(3)+Fib(2) = (Fib(2)+Fib(1)) + (Fib(1)+Fib(0)) = (1+1)+(1+0) = 3.
- ⚠️ Notice it calls itself twice → the call tree blows up fast. That's the recursion tax. 💸