Chapter 10: Recursion

1. What is Recursion? (The absolute simplest explanation)

Recursion = a function solving a problem by handing a smaller copy of the exact same problem to itself.

Two golden rules (must have both!):

1. Base case (also called stopping condition / trivial case) → When the problem is so small/simple that you can answer it directly (no more calling yourself)
2. Recursive case (the self-call part) → Break the big problem into one smaller sub-problem + do something simple with the result

Without base case → infinite loop → stack overflow crash 😭 Without recursive case → just a normal function, no recursion

Real-life Hyderabad analogy everyone gets:

Imagine you want to eat a family pack of biryani, but you’re very full. You tell your younger brother: “Eat this whole family pack for me.”

He says: “Bhai, too much! But I can eat a small plate… so give me one small plate, and I’ll ask my even smaller cousin to eat another small plate, and so on — until the last tiny cousin who can finish the last spoonful in one bite.”

→ Each brother is doing almost the same job (eat biryani), but on a smaller portion. The last tiny cousin = base case (eats the last bit → done, no more asking). Everyone else = recursive case (eats a bit → asks smaller person to eat the rest).

That’s recursion!

2. Classic #1: Factorial (n!) – The Hello World of Recursion

Factorial definition (math way): 5! = 5 × 4 × 3 × 2 × 1 = 120 Or: 5! = 5 × 4!

Let’s see what happens when we call factorial(4):

1. factorial(4) → 4 * factorial(3)
2. factorial(3) → 3 * factorial(2)
3. factorial(2) → 2 * factorial(1)
4. factorial(1) → returns 1 (base case — stops!)
5. Now go back up: 2 * 1 = 2
6. 3 * 2 = 6
7. 4 * 6 = 24

So factorial(4) returns 24

3. Classic #2: Fibonacci Sequence (very common interview question)

Fibonacci: each number is sum of two previous ones 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Warning (important lesson): This simple recursive Fibonacci is beautiful but very slow for large n (exponential time — it recalculates same values millions of times). Real code uses memoization or loop version — but for learning recursion → perfect example.

4. Visual / Fun Example – Countdown (like rocket launch)

Output:

5. The Call Stack – What’s Really Happening Inside Computer

Every time function calls itself → computer pushes new “frame” on call stack (like stacking plates).

• factorial(5) → stack: [factorial(5)]
• calls factorial(4) → stack: [factorial(5), factorial(4)]
• calls factorial(3) → stack: [factorial(5), factorial(4), factorial(3)]
• …
• reaches base → returns 1
• stack pops one by one → multiplying as it unwinds

When stack gets too deep (Python default limit ~1000 calls) → RecursionError: maximum recursion depth exceeded

6. When to Use Recursion? (Real talk)

Use when problem is naturally self-similar / divide-and-conquer:

• Tree / graph traversal (folders inside folders)
• Divide & conquer algorithms (merge sort, quick sort)
• Backtracking (sudoku solver, maze, N-Queens)
• Mathematical definitions (factorial, fibonacci, binomial coefficients)
• Tower of Hanoi puzzle (classic recursion demo)

Avoid when:

• Simple loop does same job faster & uses less memory
• Very deep recursion needed (risk of stack overflow)

7. Your Mini Challenge (try today – 10–15 min)

Open replit.com or any Python editor and implement one of these:

A. Sum of first n natural numbers recursively sum(5) = 5 + 4 + 3 + 2 + 1 = 15

B. Print a string in reverse using recursion reverse(“Hyderabad”) → “dabaredyH”

C. Power function (x^n = x × x^(n-1))

Paste your code here — I’ll check it, explain any mistake, or show cleaner version 😄

Any part still confusing?

• “Show step-by-step stack for fibonacci(4)”
• “Why recursion sometimes slower than loop?”
• “Explain memoization to make fibonacci fast”
• “Next topic please” (maybe classes/OOP or small project combining everything)

Recursion feels weird at first — but once it clicks, you’ll smile every time you use it. You’re doing awesome — keep going champ! 🚀