9. Recursion

🧸 ELI5: Recursion is a set of Russian nesting dolls (matryoshka). To find the smallest doll, you open a doll, and inside is... a smaller version of the exact same problem: "open a doll and look inside." You keep doing the same tiny step until you hit the smallest doll (the base case) that doesn't open anymore — then you're done.

🌍 Real life: Standing between two mirrors facing each other — the reflection repeats itself smaller and smaller. Folders inside folders inside folders on your computer.

📝 Pseudocode:

function factorial(n):
    if n == 0:               // base case — the smallest doll
        return 1
    return n * factorial(n - 1)   // same problem, smaller size

🐹 Go:

package main

import "fmt"

func factorial(n int) int {
	if n == 0 { // base case: stop opening dolls
		return 1
	}
	return n * factorial(n-1) // same task, one size smaller
}

func main() {
	fmt.Println(factorial(5)) // 120
}

🇨 C (deep dive: real-life-c-guide.md §5.1) — this is the guide where "the call stack" stops being an abstraction: every recursive call really is a new stack frame, and you can watch it overflow:

#include <stdio.h>

long factorial(int n) {
    if (n == 0) return 1;          // base case: stop opening dolls
    return n * factorial(n - 1);   // same task, one size smaller
}

int main(void) {
    printf("%ld\n", factorial(5)); // 120
    return 0;
}

⏱️ Complexity: Depends on the problem — factorial is O(n) calls deep. Watch out: every call uses memory (the "call stack"), so too much recursion without a base case = stack overflow (imagine infinite nesting dolls that never end — you run out of room).