Classic recursion — factorial, Fibonacci, binary search

The two parts every recursion MUST have

1. Factorial

Derive the recurrence from scratch. WHAT is $n!$ ? It's $n$ times the product of everything below it: $n! = n \times \underbrace{(n-1)(n-2)\cdots 1}_{=\,(n-1)!} = n \cdot (n-1)!$ So $n! = n\cdot(n-1)!$ — that's the recursive case. WHY base case $0!=1$ ? An empty product is $1$ (multiplying by nothing changes nothing), and it stops the chain.

def factorial(n):
    if n == 0:          # base case
        return 1
    return n * factorial(n - 1)   # recursive case: trust the smaller answer

Worked example Tracing

factorial(3) — Why each step?

factorial(3) = 3 * factorial(2)      # Why? n! = n*(n-1)!
            = 3 * (2 * factorial(1)) # Why? same rule, smaller n
            = 3 * (2 * (1 * factorial(0)))
            = 3 * (2 * (1 * 1))      # Why? base case 0! = 1
            = 6

Why this order? The multiplications wait on the stack until the base case returns, then unwind bottom-up.

2. Fibonacci

WHY two base cases? The recurrence reaches back two steps, so you need two known starting values, else you'd recurse below $F_0$ .

def fib(n):
    if n < 2:                 # base cases: F0=0, F1=1
        return n
    return fib(n - 1) + fib(n - 2)

Common mistake Steel-man: "Naive Fibonacci is fine, it's just recursion."

Why it feels right: it mirrors the math definition perfectly and gives correct answers. The trap: it recomputes the same subproblems exponentially. fib(5) calls fib(3) twice, fib(2) three times… Runtime is $\approx \Theta(\varphi^n)$ where $\varphi\approx 1.618$ . fib(40) already crawls. The fix: memoize — cache answers you've seen.

def fib(n, memo={}):
    if n < 2: return n
    if n in memo: return memo[n]
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

Now each $F_k$ is computed once → $\Theta(n)$ .

Worked example Why naive

fib is slow — the call tree

           fib(4)
         /        \
     fib(3)      fib(2)     <- fib(2) computed AGAIN below too
     /    \       /   \
  fib(2) fib(1) fib(1) fib(0)

Why repeated? fib(2) appears in two unrelated branches; no memory means redundant work.

Figure — Classic recursion — factorial, Fibonacci, binary search

3. Binary Search (recursive)

Derive the time bound. If $T(n)$ is the work for $n$ elements: $T(n) = T(n/2) + c$ (one comparison, then half the problem). Unrolling: $T(n) = c\cdot(\log_2 n) + T(1) = \Theta(\log_2 n)$ .

def binary_search(arr, target, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo > hi:                  # base case: empty range -> not found
        return -1
    mid = (lo + hi) // 2
    if arr[mid] == target:       # base case: found it
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, hi)   # search right half
    else:
        return binary_search(arr, target, lo, mid - 1)   # search left half

Recall Feynman: explain to a 12-year-old

Imagine you have to find a word in a giant dictionary. You open the middle: if your word comes earlier, you rip away the second half and only look in the first; if later, rip away the first half. Keep ripping in half — you find it super fast. That's binary search. Recursion is like a line of people passing a question back: "I don't know $5!$ , but if the person behind me tells me $4!$ , I'll just multiply by 5." Each person asks the next, until the last person knows the easy answer ( $0!=1$ ) and passes it forward. Fibonacci is "next number = sum of previous two," but if you keep asking the same little questions over and over without writing answers down, you waste tons of time — so jot them down (memoize)!

Flashcards

What two parts must every recursive function have?

A base case (stops the recursion) and a recursive case (calls itself on a smaller input).

Why is

0! = 1

the base case for factorial?

An empty product equals 1, and it stops the recursive chain.

Recurrence for factorial?

n! = n\cdot(n-1)!

, with

0!=1

Why does Fibonacci need two base cases?

The recurrence reaches back two steps (

F_{n-1}+F_{n-2}

), so two starting values are required.

Time complexity of naive recursive Fibonacci and why?

\Theta(\varphi^n)

exponential — it recomputes the same subproblems many times.

How do you make recursive Fibonacci fast?

Memoize (cache) computed values →

\Theta(n)

Precondition for binary search?

The array must be sorted.

Why is binary search

\Theta(\log n)

Each step halves the search space:

T(n)=T(n/2)+c

Binary search base cases?

lo > hi (range empty → not found) and arr[mid]==target (found).

What error does missing/unreachable base case cause in Python?

RecursionError: maximum recursion depth exceeded (stack overflow).

What data structure does the machine use to remember pending recursive calls?

The call stack (stack frames).

Connections

Recursion vs Iteration — every recursion can be rewritten as a loop + stack
Big-O Notation — how we derived $\Theta(n)$ , $\Theta(\log n)$ , $\Theta(\varphi^n)$
Memoization and Dynamic Programming — caching subproblem answers
Divide and Conquer — binary search is the simplest example
The Call Stack and Stack Frames
Sorting Algorithms — prerequisite for binary search

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Recursion ka matlab hai ek function jo apne aap ko hi call karta hai, lekin har baar thode chote problem pe. Do cheezein har recursion mein zaroori hain: base case (sabse chota case jahan seedha answer return ho jaye, taaki chain ruk jaye) aur recursive case (jahan tum chote version pe khud ko call karke result jodte ho). Soch lo jaise ek line mein log khade hain — har banda peeche wale se poochta hai, aur aakhri banda jise easy answer pata hai wo wapas bhej deta hai. Yahi "Base, Break, Believe" wala funda hai.

Factorial simple hai: $n! = n \times (n-1)!$ , aur $0! = 1$ . Bas isi rule ko code mein likh do. Fibonacci mein $F_n = F_{n-1} + F_{n-2}$ , isliye do base cases chahiye ( $F_0=0, F_1=1$ ). Par ek warning: naive Fibonacci bohot slow hai kyunki wo same chote sawaal baar-baar solve karta hai — fib(40) hi atak jaata hai. Iska fix hai memoization, yaani answers ko ek dictionary mein cache kar lo, phir har value sirf ek baar calculate hoti hai.

Binary search sabse pyaara example hai. Condition: array sorted hona chahiye. Tum beech wale (mid) element se compare karte ho — agar target chota hai to left half mein dhoondo, bada hai to right half mein. Har step mein aadha array fenk dete ho, isliye time $\log_2 n$ ho jaata hai. Agar $n=10\,$ lakh ho, tab bhi sirf ~20 steps! Bas yaad rakho: unsorted array pe binary search galat answer dega — pehle sort karo.

Classic recursion — factorial, Fibonacci, binary search

The two parts every recursion MUST have

1. Factorial

2. Fibonacci

3. Binary Search (recursive)

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Introduction to Programming (Python)

Connections

call	lo	hi	mid	arr[mid]	decision (Why?)
1	0	5	2	5	$5<7$ → go right, `lo=3`
2	3	5	4	9	$9>7$ → go left, `hi=3`
3	3	3	3	7	found → return `3`
Why halving each time? Sorted order guarantees everything left of `mid` is smaller, right is bigger — so one comparison eliminates a whole half safely.

Problem	Recurrence	Time
factorial	$T(n)=T(n-1)+c$	$\Theta(n)$
fib (naive)	$T(n)=T(n-1)+T(n-2)+c$	$\Theta(\varphi^n)$
fib (memo)	each $F_k$ once	$\Theta(n)$
binary search	$T(n)=T(n/2)+c$	$\Theta(\log n)$