5.8 Recursion

Overview

Recursion is a programming technique where a function calls itself to solve a problem. It's a powerful approach for problems that can be broken down into smaller, similar subproblems. Understanding recursion is essential for algorithms, data structures, and functional programming.

•What is Recursion?
•Anatomy of a Recursive Function
•How Recursion Works
•Base Case and Recursive Case
•Classic Recursion Examples
•Recursion with Arrays
•Recursion with Objects
•Tail Recursion
•Recursion vs Iteration
•Common Pitfalls
•When to Use Recursion
•Best Practices

What is Recursion?

Recursion occurs when a function calls itself to solve a smaller instance of the same problem.

┌─────────────────────────────────────────────────────────┐
│                    RECURSION                             │
├─────────────────────────────────────────────────────────┤
│                                                          │
│   function solve(problem) {                              │
│       if (problem is simple) {                          │
│           return simple solution;    ← Base Case        │
│       } else {                                          │
│           return solve(smaller problem); ← Recursive    │
│       }                                                  │
│   }                                                      │
│                                                          │
│   Key Components:                                        │
│   1. Base Case    - When to stop                        │
│   2. Recursive Case - How to reduce the problem         │
│                                                          │
└─────────────────────────────────────────────────────────┘

Simple Example

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

  // Recursive case: print and call with smaller value
  console.log(n);
  countdown(n - 1);
}

countdown(5);
// 5, 4, 3, 2, 1, Done!

Anatomy of a Recursive Function

Every recursive function has two essential parts:

function recursiveFunction(input) {
  // 1. BASE CASE - Condition to stop recursion
  if (baseCondition) {
    return baseValue;
  }

  // 2. RECURSIVE CASE - Call itself with modified input
  return recursiveFunction(modifiedInput);
}

Example: Factorial

function factorial(n) {
  // Base case: factorial of 0 or 1 is 1
  if (n <= 1) {
    return 1;
  }

  // Recursive case: n! = n * (n-1)!
  return n * factorial(n - 1);
}

console.log(factorial(5)); // 120

How Recursion Works

Each recursive call creates a new execution context on the call stack.

factorial(5)
│
├─→ 5 * factorial(4)
│       │
│       ├─→ 4 * factorial(3)
│       │       │
│       │       ├─→ 3 * factorial(2)
│       │       │       │
│       │       │       ├─→ 2 * factorial(1)
│       │       │       │       │
│       │       │       │       └─→ returns 1 (base case)
│       │       │       │
│       │       │       └─→ returns 2 * 1 = 2
│       │       │
│       │       └─→ returns 3 * 2 = 6
│       │
│       └─→ returns 4 * 6 = 24
│
└─→ returns 5 * 24 = 120

Call Stack Visualization

┌────────────────────────────────────┐
│  Call Stack (going down)           │
├────────────────────────────────────┤
│                                    │
│  factorial(1) → returns 1          │  ← Base case hit
│  factorial(2) → waiting...         │
│  factorial(3) → waiting...         │
│  factorial(4) → waiting...         │
│  factorial(5) → waiting...         │
│                                    │
├────────────────────────────────────┤
│  Call Stack (unwinding)            │
├────────────────────────────────────┤
│                                    │
│  factorial(2) → returns 2 * 1 = 2  │
│  factorial(3) → returns 3 * 2 = 6  │
│  factorial(4) → returns 4 * 6 = 24 │
│  factorial(5) → returns 5 * 24=120 │
│                                    │
└────────────────────────────────────┘

Base Case and Recursive Case

Base Case

The condition that stops the recursion. Without it, you get infinite recursion!

// ❌ Missing base case - infinite recursion!
function bad(n) {
  return n * bad(n - 1); // Never stops!
}

// ✅ With base case
function good(n) {
  if (n <= 1) return 1; // Stops here
  return n * good(n - 1);
}

Multiple Base Cases

function fibonacci(n) {
  // Multiple base cases
  if (n === 0) return 0;
  if (n === 1) return 1;

  // Recursive case
  return fibonacci(n - 1) + fibonacci(n - 2);
}

Recursive Case

Must progress toward the base case:

// ❌ Not progressing toward base case
function wrong(n) {
  if (n === 0) return 0;
  return wrong(n); // n never changes!
}

// ✅ Progressing toward base case
function right(n) {
  if (n === 0) return 0;
  return right(n - 1); // n decreases toward 0
}

Classic Recursion Examples

1. Factorial

// n! = n × (n-1) × (n-2) × ... × 1
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

console.log(factorial(5)); // 120
console.log(factorial(0)); // 1

2. Fibonacci

// 0, 1, 1, 2, 3, 5, 8, 13, 21...
function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(7)); // 13

3. Power/Exponentiation

// base^exponent
function power(base, exponent) {
  if (exponent === 0) return 1;
  return base * power(base, exponent - 1);
}

console.log(power(2, 8)); // 256

4. Sum of Array

function sum(arr) {
  if (arr.length === 0) return 0;
  return arr[0] + sum(arr.slice(1));
}

console.log(sum([1, 2, 3, 4, 5])); // 15

5. Reverse String

function reverse(str) {
  if (str.length <= 1) return str;
  return reverse(str.slice(1)) + str[0];
}

console.log(reverse('hello')); // "olleh"

6. Check Palindrome

function isPalindrome(str) {
  if (str.length <= 1) return true;
  if (str[0] !== str[str.length - 1]) return false;
  return isPalindrome(str.slice(1, -1));
}

console.log(isPalindrome('racecar')); // true
console.log(isPalindrome('hello')); // false

Recursion with Arrays

Find Element

function includes(arr, target, index = 0) {
  if (index >= arr.length) return false;
  if (arr[index] === target) return true;
  return includes(arr, target, index + 1);
}

console.log(includes([1, 2, 3, 4], 3)); // true
console.log(includes([1, 2, 3, 4], 5)); // false

Map with Recursion

function map(arr, fn) {
  if (arr.length === 0) return [];
  return [fn(arr[0]), ...map(arr.slice(1), fn)];
}

console.log(map([1, 2, 3], (n) => n * 2)); // [2, 4, 6]

Filter with Recursion

function filter(arr, predicate) {
  if (arr.length === 0) return [];

  const rest = filter(arr.slice(1), predicate);
  return predicate(arr[0]) ? [arr[0], ...rest] : rest;
}

console.log(filter([1, 2, 3, 4, 5], (n) => n % 2 === 0)); // [2, 4]

Flatten Nested Arrays

function flatten(arr) {
  let result = [];

  for (const item of arr) {
    if (Array.isArray(item)) {
      result = result.concat(flatten(item));
    } else {
      result.push(item);
    }
  }

  return result;
}

console.log(flatten([1, [2, [3, [4]]]])); // [1, 2, 3, 4]

Recursion with Objects

Deep Clone

function deepClone(obj) {
  // Handle non-objects
  if (obj === null || typeof obj !== 'object') {
    return obj;
  }

  // Handle arrays
  if (Array.isArray(obj)) {
    return obj.map((item) => deepClone(item));
  }

  // Handle objects
  const clone = {};
  for (const key in obj) {
    if (obj.hasOwnProperty(key)) {
      clone[key] = deepClone(obj[key]);
    }
  }
  return clone;
}

const original = { a: 1, b: { c: 2, d: [3, 4] } };
const cloned = deepClone(original);

Deep Freeze

function deepFreeze(obj) {
  Object.freeze(obj);

  for (const key of Object.keys(obj)) {
    if (typeof obj[key] === 'object' && obj[key] !== null) {
      deepFreeze(obj[key]);
    }
  }

  return obj;
}

Find Nested Value

function findValue(obj, key) {
  if (obj.hasOwnProperty(key)) {
    return obj[key];
  }

  for (const k in obj) {
    if (typeof obj[k] === 'object' && obj[k] !== null) {
      const result = findValue(obj[k], key);
      if (result !== undefined) {
        return result;
      }
    }
  }

  return undefined;
}

const data = {
  user: {
    profile: {
      name: 'Alice',
    },
  },
};

console.log(findValue(data, 'name')); // "Alice"

Count Nested Keys

function countKeys(obj) {
  let count = 0;

  for (const key in obj) {
    count++; // Count this key
    if (typeof obj[key] === 'object' && obj[key] !== null) {
      count += countKeys(obj[key]); // Count nested keys
    }
  }

  return count;
}

Tail Recursion

Tail recursion is when the recursive call is the last operation in the function.

// Not tail recursive - multiplication happens after recursive call
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1); // Must wait for result
}

// Tail recursive - uses accumulator
function factorialTail(n, accumulator = 1) {
  if (n <= 1) return accumulator;
  return factorialTail(n - 1, n * accumulator); // Nothing after call
}

console.log(factorialTail(5)); // 120

Tail Recursive Examples

// Tail recursive sum
function sumTail(arr, accumulator = 0, index = 0) {
  if (index >= arr.length) return accumulator;
  return sumTail(arr, accumulator + arr[index], index + 1);
}

// Tail recursive fibonacci
function fibTail(n, a = 0, b = 1) {
  if (n === 0) return a;
  if (n === 1) return b;
  return fibTail(n - 1, b, a + b);
}

console.log(fibTail(50)); // 12586269025 (fast!)

Note: JavaScript engines don't always optimize tail calls, but the pattern is still useful for clarity.

Recursion vs Iteration

Comparison

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

// Iterative factorial
function factorialIterative(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

When to Use Each

Recursion	Iteration
Tree structures	Simple loops
Divide & conquer	Performance critical
Cleaner code	Large datasets
Nested data	Avoiding stack overflow

Same Problem, Both Ways

// Sum array - Recursive
function sumRecursive(arr) {
  if (arr.length === 0) return 0;
  return arr[0] + sumRecursive(arr.slice(1));
}

// Sum array - Iterative
function sumIterative(arr) {
  let total = 0;
  for (const num of arr) {
    total += num;
  }
  return total;
}

// Both work!
console.log(sumRecursive([1, 2, 3, 4, 5])); // 15
console.log(sumIterative([1, 2, 3, 4, 5])); // 15

Common Pitfalls

1. Missing Base Case

// ❌ Infinite recursion - no base case
function infinite(n) {
  return infinite(n - 1);
}

// ✅ Has base case
function finite(n) {
  if (n <= 0) return 0;
  return finite(n - 1);
}

2. Not Progressing Toward Base Case

// ❌ n never changes
function stuck(n) {
  if (n === 0) return 0;
  return stuck(n); // Same n every time!
}

// ✅ n decreases
function progress(n) {
  if (n === 0) return 0;
  return progress(n - 1); // Moving toward 0
}

3. Stack Overflow

// ❌ Too many recursive calls
function countToMillion(n) {
  if (n >= 1000000) return n;
  return countToMillion(n + 1); // Will overflow!
}

// ✅ Use iteration for large counts
function countToMillionSafe(n) {
  while (n < 1000000) n++;
  return n;
}

4. Inefficient Fibonacci

// ❌ Exponential time - very slow!
function fibSlow(n) {
  if (n <= 1) return n;
  return fibSlow(n - 1) + fibSlow(n - 2);
}

// ✅ Memoized - linear time
function fibMemo(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;

  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}

console.log(fibMemo(50)); // Fast!

When to Use Recursion

Good Use Cases

•Tree/Graph Traversal

function traverseTree(node) {
  console.log(node.value);
  for (const child of node.children) {
    traverseTree(child);
  }
}

•Nested Data Structures

function processNestedData(data) {
  if (typeof data !== 'object') {
    return transform(data);
  }
  // Recursively process nested objects/arrays
}

•Divide and Conquer Algorithms

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

•Mathematical Definitions

// GCD - Euclidean algorithm
function gcd(a, b) {
  if (b === 0) return a;
  return gcd(b, a % b);
}

Avoid Recursion When

•Simple iteration will do
•Very large datasets (stack overflow risk)
•Performance is critical
•Recursion depth is unpredictable

Best Practices

1. Always Have a Base Case

function process(data) {
  // ✅ Clear base case first
  if (data === null || data === undefined) {
    return defaultValue;
  }

  // Then recursive logic
  return process(data.next);
}

2. Ensure Progress Toward Base Case

// ✅ Each call gets closer to base case
function countdown(n) {
  if (n <= 0) return;
  console.log(n);
  countdown(n - 1); // n decreases
}

3. Use Memoization for Overlapping Subproblems

function memoize(fn) {
  const cache = {};
  return function (...args) {
    const key = JSON.stringify(args);
    if (!(key in cache)) {
      cache[key] = fn.apply(this, args);
    }
    return cache[key];
  };
}

const fib = memoize((n) => {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
});

4. Consider Tail Recursion

// ✅ Tail recursive with accumulator
function sum(arr, total = 0, index = 0) {
  if (index >= arr.length) return total;
  return sum(arr, total + arr[index], index + 1);
}

5. Test Edge Cases

// Test with:
factorial(0); // Edge: zero
factorial(1); // Edge: one
factorial(-1); // Edge: negative
factorial(170); // Edge: large number

Summary

┌──────────────────────────────────────────────────────────┐
│                      RECURSION                            │
├──────────────────────────────────────────────────────────┤
│                                                           │
│  COMPONENTS:                                              │
│  • Base Case - When to stop                              │
│  • Recursive Case - Call self with smaller problem       │
│                                                           │
│  CLASSIC EXAMPLES:                                        │
│  • Factorial: n! = n × (n-1)!                            │
│  • Fibonacci: fib(n) = fib(n-1) + fib(n-2)               │
│  • Sum: sum([a,...rest]) = a + sum(rest)                 │
│                                                           │
│  USE CASES:                                               │
│  • Tree/graph traversal                                   │
│  • Nested data structures                                 │
│  • Divide and conquer algorithms                          │
│  • Mathematical definitions                               │
│                                                           │
│  OPTIMIZATION:                                            │
│  • Memoization for overlapping subproblems               │
│  • Tail recursion with accumulators                      │
│  • Convert to iteration for large inputs                 │
│                                                           │
│  PITFALLS:                                                │
│  • Missing base case → infinite recursion                │
│  • Not progressing → infinite recursion                  │
│  • Too deep → stack overflow                             │
│  • Inefficient → exponential time                        │
│                                                           │
└──────────────────────────────────────────────────────────┘

Next Steps

•Practice with the examples in examples.js
•Complete the exercises in exercises.js
•Learn about advanced algorithms using recursion
•Explore tree and graph data structures

README