Skip to content
Deadline to Die

Module 1: Recursive Thinking (The Mirror Room)

📚 Module 1: Recursive Thinking

Course ID: DSA-203
Subject: The Mirror Room

Imagine you are in a room with a mirror on the front wall and a mirror on the back wall. You see a reflection of yourself, inside a reflection, inside a reflection… forever. That is Recursion.

🏗️ Step 1: The Two Rules

To prevent recursion from going on forever (and crashing your computer), you MUST have two things:

  1. The Base Case: The “Exit Door.” This is a simple condition where the function Stops calling itself.
  2. The Recursive Step: A call to the function itself, but with a Simpler input that brings it closer to the exit door.

🧩 The Analogy: Russian Nesting Dolls

  • The Task: Find the tiny gold ring inside the smallest doll.
  • The Step: Open the current doll. Is there a ring? No? Then look inside the next smaller doll (Recursion).
  • The Base Case: You find the ring! (Exit).

🏗️ Step 2: In Code (Factorial)

Factorial of 5 (5!5!) is 5×4×3×2×15 \times 4 \times 3 \times 2 \times 1.

def factorial(n):
    # 1. BASE CASE (The smallest doll)
    if n == 1:
        return 1
    
    # 2. RECURSIVE STEP (Moving closer to 1)
    return n * factorial(n - 1)

🏗️ Step 3: The Call Stack (The “Wait”)

Recursion uses the System Stack (Milestone 3).

  • factorial(3) calls factorial(2) and Waits.
  • factorial(2) calls factorial(1) and Waits.
  • factorial(1) returns 1.
  • Now the “Waiting” functions wake up and finish their math.

🥅 Module 1 Review

  1. Recursion: A function calling itself.
  2. Base Case: The stopping condition.
  3. Stack Overflow: What happens when you forget the base case and the computer runs out of memory.

:::tip Slow Learner Note If you can’t figure out the recursion, try to solve it with a while loop first. Any recursive function can be written as a loop (Iteration)! :::