Recursion - Intro to Programming Tutorial

Quick Summary

Recursion breaks a big problem into smaller versions of itself. Always include a base case so the function stops, or you'll hit a call stack error. Recursion is elegant for tree structures and mathematical sequences.

What is Recursion?

Recursion is when a function calls itself to solve a problem. It's like Russian nesting dolls — each doll contains a smaller version of itself.

The Two Essential Parts

Base Case: When to STOP recursing
Recursive Case: Call itself with a smaller problem

function countdown(n) {
  // Base case: stop at 0
  if (n <= 0) {
    console.log("Done!");
    return;
  }

  // Recursive case: count down
  console.log(n);
  countdown(n - 1);
}

Classic Example: Factorial

Factorial of n (written n!) = n × (n-1) × (n-2) × ... × 1

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

function factorial(n) {
  if (n <= 1) return 1;        // Base case
  return n * factorial(n - 1); // Recursive case
}

// How it works:
// factorial(5)
// → 5 * factorial(4)
// → 5 * 4 * factorial(3)
// → 5 * 4 * 3 * factorial(2)
// → 5 * 4 * 3 * 2 * factorial(1)
// → 5 * 4 * 3 * 2 * 1
// → 120

When to Use Recursion

Tree/graph traversal
Nested data structures
Mathematical sequences (factorial, Fibonacci)
Divide-and-conquer algorithms

Recursion vs Loops

Many recursive solutions can be written as loops:

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

// Loop (often more efficient)
function sumLoop(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {
    total += i;
  }
  return total;
}

Watch Out: Stack Overflow

Each recursive call uses memory. Too many calls = crash.

// This will crash!
function infinite() {
  return infinite(); // No base case!
}

Try It Yourself

Here's a practical example you can try. Copy this code and run it in your browser's console (press F12 to open developer tools) or in the Code Playground.

// Factorial: n! = n × (n-1) × ... × 1
function factorial(n) {
  if (n <= 1) return 1;        // Base case
  return n * factorial(n - 1); // Recursive case
}
console.log(factorial(5)); // 120

// Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, ...
function fibonacci(n) {
  if (n <= 1) return n;        // Base cases: fib(0)=0, fib(1)=1
  return fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(7)); // 13

// Sum of array using recursion
function sumArray(arr) {
  if (arr.length === 0) return 0;   // Base case
  return arr[0] + sumArray(arr.slice(1)); // Recursive case
}
console.log(sumArray([1, 2, 3, 4, 5])); // 15

// Countdown example
function countdown(n) {
  if (n <= 0) {
    console.log("Blast off!");
    return;
  }
  console.log(n);
  countdown(n - 1);
}
countdown(3); // 3, 2, 1, "Blast off!"

// Nested object traversal
function findValue(obj, key) {
  if (obj[key]) return obj[key];
  for (const k in obj) {
    if (typeof obj[k] === 'object') {
      const result = findValue(obj[k], key);
      if (result) return result;
    }
  }
  return null;
}

Key Takeaways

✓Solve a problem by calling a function inside itself.
✓Practice with real code examples to solidify your understanding
✓This concept builds the foundation for more advanced topics