Recursion Fundamentals

🪆 The Magic of Recursion: A Function That Calls Itself

🎭 The Story of the Russian Dolls

Imagine you have a beautiful Russian nesting doll (Matryoshka). You open it, and inside is a smaller doll. You open that one, and there’s an even smaller doll inside. You keep opening dolls until you find the tiniest one that cannot be opened.

That’s recursion! A function that opens itself, again and again, until it reaches the smallest version that just gives an answer.

🌟 Recursion Fundamentals

What IS Recursion?

Recursion is when a function calls itself to solve a problem.

Think of it like this:

• Mom asks you to count all apples in a bag
• You take ONE apple out, then ask your friend to count the rest
• Your friend takes ONE apple out, asks another friend to count the rest
• Eventually, someone sees an empty bag and says “ZERO!”
• Everyone adds their apple back: “0 + 1 + 1 + 1 = 3 apples!”

Simple Code Example

function countDown(number) {
  // Print current number
  console.log(number);

  // Call myself with smaller number
  countDown(number - 1);
}

countDown(5);
// Prints: 5, 4, 3, 2, 1, 0, -1, -2...
// WAIT! This never stops! 😱

Problem: Without a stopping point, recursion runs forever! We need a base case.

🛑 Recursion Base Cases

The Stopping Signal

A base case is the moment when recursion says “STOP! I have my answer!”

Remember the Russian dolls? The base case is the tiny doll that cannot be opened. Without it, you’d try to open dolls forever!

Fixed Code with Base Case

function countDown(number) {
  // 🛑 BASE CASE: Stop when we reach 0
  if (number < 0) {
    return; // Done! Stop calling myself
  }

  console.log(number);
  countDown(number - 1);
}

countDown(5);
// Prints: 5, 4, 3, 2, 1, 0 ✅ Then stops!

🎯 Real Example: Factorial

Factorial means multiplying a number by all smaller numbers down to 1.

• 5! = 5 × 4 × 3 × 2 × 1 = 120

function factorial(n) {
  // 🛑 BASE CASE
  if (n <= 1) {
    return 1;
  }

  // RECURSIVE CASE
  return n * factorial(n - 1);
}

factorial(5); // Returns 120

How it works:

factorial(5)
  → 5 × factorial(4)
    → 4 × factorial(3)
      → 3 × factorial(2)
        → 2 × factorial(1)
          → 1 (BASE CASE! Stop here!)
        → 2 × 1 = 2
      → 3 × 2 = 6
    → 4 × 6 = 24
  → 5 × 24 = 120 ✅

🔄 The Two Parts of Every Recursion

graph TD
    A["🎯 Start Function"] --> B{Base Case?}
    B -->|YES| C["🛑 Return Answer"]
    B -->|NO| D["📞 Call Myself"]
    D --> E["With Smaller Problem"]
    E --> A

🔧 Recursion to Iteration

The Big Secret

Every recursive function can be written as a loop!

Sometimes loops are easier to understand. Sometimes recursion is cleaner. You can convert between them!

Example: Sum Numbers from 1 to N

Recursive Way:

function sumRecursive(n) {
  if (n <= 0) return 0;
  return n + sumRecursive(n - 1);
}

sumRecursive(5); // 5+4+3+2+1 = 15

Iterative Way (Loop):

function sumIterative(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {
    total = total + i;
  }
  return total;
}

sumIterative(5); // 15

Conversion Pattern

Factorial: Both Ways

// RECURSIVE
function factorialRec(n) {
  if (n <= 1) return 1;
  return n * factorialRec(n - 1);
}

// ITERATIVE
function factorialLoop(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result = result * i;
  }
  return result;
}

🎯 When to Use Which?

graph TD
    A["Problem Type?"] --> B{Tree/Nested Structure?}
    B -->|Yes| C["✅ Use Recursion"]
    B -->|No| D{Simple Counting?}
    D -->|Yes| E["✅ Use Loop"]
    D -->|No| F{Deep Nesting?}
    F -->|Yes| G["✅ Use Loop"]
    F -->|No| C

💡 Key Takeaways

1. Recursion = A function that calls itself
2. Base Case = The stop signal (NEVER forget it!)
3. Recursive Case = Calls itself with a smaller problem
4. Every recursion can become a loop (and vice versa)
5. Choose wisely based on problem structure

🎪 Practice Problem

Challenge: Write a recursive function to count digits in a number.

Example: countDigits(12345) should return 5

Hint:

• Base case: Single digit numbers have 1 digit
• Recursive case: Remove last digit, add 1

function countDigits(n) {
  // Base case: 0-9 have 1 digit
  if (n < 10) return 1;

  // Remove last digit, count the rest
  return 1 + countDigits(Math.floor(n / 10));
}

countDigits(12345); // Returns 5 ✅

🌟 Remember: Recursion is like a mirror reflecting a mirror. Beautiful, but you need a wall (base case) to stop the infinite reflections!