JavaScript Design Patterns

Recursion

Functions that call themselves

Find videos you like?

Save to resource drawer for future reference!

Recursion: A Function Calling Itself

Recursion is when a function calls itself to solve a problem by breaking it into smaller, similar sub-problems. Perfect for tree structures, factorial, Fibonacci, and divide-and-conquer!

Two Key Parts

1. Base Case - When to stop (prevents infinite loop)
2. Recursive Case - Function calls itself with smaller input

Recursion Visualization

Watch factorial(5) execute step by step

Click 'Start Animation' to visualize factorial(5)

Call Stack (Top to Bottom):

Call stack is empty. Click Start to begin!

Calling Phase

Returning Phase

Basic Recursion

Base case + recursive case

Iterative (Loop)

// Countdown with loop
function countdown(n) {
  for (let i = n; i > 0; i--) {
    console.log(i);
  }
  console.log('Done!');
}

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

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

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

✅ Recursive

// Countdown with recursion
function countdown(n) {
  if (n <= 0) {           // Base case
    console.log('Done!');
    return;
  }
  console.log(n);
  countdown(n - 1);       // Recursive case
}

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

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

console.log(factorial(5)); // 120
// 5 * 4 * 3 * 2 * 1 = 120

How Recursion Works

Understanding the call stack

javascript

code

DarkEditable

Console Output

Click "Run Code" to see output here...

Common Recursive Patterns

Fibonacci, sum, power

Classic Examples

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

console.log(fibonacci(6)); // 8

// 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

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

console.log(power(2, 5)); // 32

// Reverse string
function reverse(str) {
  if (str === '') return '';
  return reverse(str.slice(1)) + str[0];
}

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

Array and Object Recursion

Nested structures

javascript

code

DarkEditable

// Find max in array
function findMax(arr) {
  if (arr.length === 1) return arr[0];
  const restMax = findMax(arr.slice(1));
  return arr[0] > restMax ? arr[0] : restMax;
}

console.log(findMax([3, 7, 2, 9, 1])); // 9

// Flatten nested array
function flatten(arr) {
  let result = [];
  for (const item of arr) {
    if (Array.isArray(item)) {
      result = result.concat(flatten(item)); // Recursive
    } else {
      result.push(item);
    }
  }
  return result;
}

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

// Deep clone object
function deepClone(obj) {
  if (obj === null || typeof obj !== 'object') {
    return obj;
  }
  
  if (Array.isArray(obj)) {
    return obj.map(item => deepClone(item));
  }
  
  const cloned = {};
  for (const key in obj) {
    cloned[key] = deepClone(obj[key]); // Recursive
  }
  return cloned;
}

const original = { a: 1, b: { c: 2, d: [3, 4] } };
const copy = deepClone(original);
console.log(copy); // Deep copy of original

// Count objects in nested structure
function countObjects(obj) {
  let count = 1; // Count current object
  
  for (const key in obj) {
    if (typeof obj[key] === 'object' && obj[key] !== null) {
      count += countObjects(obj[key]); // Recursive
    }
  }
  
  return count;
}

const nested = { a: { b: { c: {} } }, d: {} };
console.log(countObjects(nested)); // 4

Console Output

Click "Run Code" to see output here...

Tree Traversal

Perfect use case for recursion

javascript

code

DarkEditable

// Binary tree node
class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// Create a tree
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

// Pre-order traversal (Root, Left, Right)
function preOrder(node) {
  if (node === null) return;
  
  console.log(node.value);
  preOrder(node.left);
  preOrder(node.right);
}

preOrder(root); // 1 2 4 5 3

// In-order traversal (Left, Root, Right)
function inOrder(node) {
  if (node === null) return;
  
  inOrder(node.left);
  console.log(node.value);
  inOrder(node.right);
}

inOrder(root); // 4 2 5 1 3

// Post-order traversal (Left, Right, Root)
function postOrder(node) {
  if (node === null) return;
  
  postOrder(node.left);
  postOrder(node.right);
  console.log(node.value);
}

postOrder(root); // 4 5 2 3 1

// Sum all values in tree
function sumTree(node) {
  if (node === null) return 0;
  
  return node.value + sumTree(node.left) + sumTree(node.right);
}

console.log(sumTree(root)); // 15

// Find max depth
function maxDepth(node) {
  if (node === null) return 0;
  
  const leftDepth = maxDepth(node.left);
  const rightDepth = maxDepth(node.right);
  
  return Math.max(leftDepth, rightDepth) + 1;
}

console.log(maxDepth(root)); // 3

Console Output

Click "Run Code" to see output here...

Tail Recursion Optimization

When recursion is the last operation

Not Tail Recursive

// Must wait for recursive call
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
  //     ^ operation after recursion
}

// Stack grows:
// factorial(5)
//   5 * factorial(4)
//     4 * factorial(3)
//       3 * factorial(2)
//         2 * factorial(1)
//           1

// Each call must wait!

✅ Tail Recursive

// Recursion is last operation
function factorial(n, acc = 1) {
  if (n <= 1) return acc;
  return factorial(n - 1, n * acc);
  //     ^ nothing after recursion
}

// Accumulator carries result:
// factorial(5, 1)
// factorial(4, 5)
// factorial(3, 20)
// factorial(2, 60)
// factorial(1, 120)
// return 120

// Can be optimized by compiler!

Common Pitfalls

Avoid these mistakes

❌ Missing Base Case

function countdown(n) {
  console.log(n);
  countdown(n - 1); // Never stops!
}
// RangeError: Maximum call stack size exceeded

❌ Wrong Base Case

function fibonacci(n) {
  if (n === 1) return 1; // Missing n === 0
  return fibonacci(n - 1) + fibonacci(n - 2);
}
fibonacci(0); // Infinite recursion!

❌ Not Moving Toward Base Case

function sum(arr) {
  if (arr.length === 0) return 0;
  return arr[0] + sum(arr); // Not getting smaller!
}
// Infinite recursion

Key Takeaways

🔁

Self-Calling

Function calls itself
Breaks problem into smaller parts

🛑

Base Case

Critical stopping condition
Prevents infinite loops

🌲

Perfect For Trees

Tree traversal, nested objects
Natural fit for hierarchical data

📊

Call Stack

Each call uses memory
Watch for stack overflow

Pro Tip

When stuck, ask: "What's the simplest case?" (base case) and "How can I make the problem smaller?" (recursive case). Always ensure you're moving toward the base case!

Previous Topic

Function Composition

Combining simple functions to build complex operations.

Next Topic

Memoization

Caching function results for performance optimization.

Ask a Question

Have a question about Recursion? Ask our AI assistant.

🔐 Login to use AI Assistant

JavaScript Code Editor

Write and experiment with JavaScript code.

Output

Click "Run Code" to see the output.

JavaScript Design Patterns

Recursion

Functions that call themselves

Find videos you like?

Save to resource drawer for future reference!

Recursion: A Function Calling Itself

Recursion is when a function calls itself to solve a problem by breaking it into smaller, similar sub-problems. Perfect for tree structures, factorial, Fibonacci, and divide-and-conquer!

Two Key Parts

1. Base Case - When to stop (prevents infinite loop)
2. Recursive Case - Function calls itself with smaller input

Recursion Visualization

Watch factorial(5) execute step by step

Click 'Start Animation' to visualize factorial(5)

Call Stack (Top to Bottom):

Call stack is empty. Click Start to begin!

Calling Phase

Returning Phase

Basic Recursion

Base case + recursive case

Iterative (Loop)

// Countdown with loop
function countdown(n) {
  for (let i = n; i > 0; i--) {
    console.log(i);
  }
  console.log('Done!');
}

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

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

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

✅ Recursive

// Countdown with recursion
function countdown(n) {
  if (n <= 0) {           // Base case
    console.log('Done!');
    return;
  }
  console.log(n);
  countdown(n - 1);       // Recursive case
}

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

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

console.log(factorial(5)); // 120
// 5 * 4 * 3 * 2 * 1 = 120

How Recursion Works

Understanding the call stack

javascript

code

DarkEditable

Console Output

Click "Run Code" to see output here...

Common Recursive Patterns

Fibonacci, sum, power

Classic Examples

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

console.log(fibonacci(6)); // 8

// 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

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

console.log(power(2, 5)); // 32

// Reverse string
function reverse(str) {
  if (str === '') return '';
  return reverse(str.slice(1)) + str[0];
}

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

Array and Object Recursion

Nested structures

javascript

code

DarkEditable

// Find max in array
function findMax(arr) {
  if (arr.length === 1) return arr[0];
  const restMax = findMax(arr.slice(1));
  return arr[0] > restMax ? arr[0] : restMax;
}

console.log(findMax([3, 7, 2, 9, 1])); // 9

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

const original = { a: 1, b: { c: 2, d: [3, 4] } };
const copy = deepClone(original);
console.log(copy); // Deep copy of original

const nested = { a: { b: { c: {} } }, d: {} };
console.log(countObjects(nested)); // 4

Console Output

Click "Run Code" to see output here...

Tree Traversal

Perfect use case for recursion

javascript

code

DarkEditable

// Binary tree node
class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// Create a tree
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

// Pre-order traversal (Root, Left, Right)
function preOrder(node) {
  if (node === null) return;
  
  console.log(node.value);
  preOrder(node.left);
  preOrder(node.right);
}

preOrder(root); // 1 2 4 5 3

// In-order traversal (Left, Root, Right)
function inOrder(node) {
  if (node === null) return;
  
  inOrder(node.left);
  console.log(node.value);
  inOrder(node.right);
}

inOrder(root); // 4 2 5 1 3

// Post-order traversal (Left, Right, Root)
function postOrder(node) {
  if (node === null) return;
  
  postOrder(node.left);
  postOrder(node.right);
  console.log(node.value);
}

postOrder(root); // 4 5 2 3 1

// Sum all values in tree
function sumTree(node) {
  if (node === null) return 0;
  
  return node.value + sumTree(node.left) + sumTree(node.right);
}

console.log(sumTree(root)); // 15

console.log(maxDepth(root)); // 3

Console Output

Click "Run Code" to see output here...

Tail Recursion Optimization

When recursion is the last operation

Not Tail Recursive

// Must wait for recursive call
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
  //     ^ operation after recursion
}

// Stack grows:
// factorial(5)
//   5 * factorial(4)
//     4 * factorial(3)
//       3 * factorial(2)
//         2 * factorial(1)
//           1

// Each call must wait!

✅ Tail Recursive

// Recursion is last operation
function factorial(n, acc = 1) {
  if (n <= 1) return acc;
  return factorial(n - 1, n * acc);
  //     ^ nothing after recursion
}

// Accumulator carries result:
// factorial(5, 1)
// factorial(4, 5)
// factorial(3, 20)
// factorial(2, 60)
// factorial(1, 120)
// return 120

// Can be optimized by compiler!

Common Pitfalls

Avoid these mistakes

❌ Missing Base Case

function countdown(n) {
  console.log(n);
  countdown(n - 1); // Never stops!
}
// RangeError: Maximum call stack size exceeded

❌ Wrong Base Case

function fibonacci(n) {
  if (n === 1) return 1; // Missing n === 0
  return fibonacci(n - 1) + fibonacci(n - 2);
}
fibonacci(0); // Infinite recursion!

❌ Not Moving Toward Base Case

function sum(arr) {
  if (arr.length === 0) return 0;
  return arr[0] + sum(arr); // Not getting smaller!
}
// Infinite recursion

Key Takeaways

🔁

Self-Calling

Function calls itself
Breaks problem into smaller parts

🛑

Base Case

Critical stopping condition
Prevents infinite loops

🌲

Perfect For Trees

Tree traversal, nested objects
Natural fit for hierarchical data

📊

Call Stack

Each call uses memory
Watch for stack overflow

Pro Tip

When stuck, ask: "What's the simplest case?" (base case) and "How can I make the problem smaller?" (recursive case). Always ensure you're moving toward the base case!

Coder Pod - Learn Programming Online | AI Coding Tutor & Interview Practice

Function Composition

Memoization

JavaScript Code Editor

Building Your Learning Module...

Recursion

Recursion: A Function Calling Itself

Two Key Parts

Call Stack (Top to Bottom):

Iterative (Loop)

✅ Recursive

How Recursion Works

Classic Examples

Array and Object Recursion

Tree Traversal

Not Tail Recursive

✅ Tail Recursive

❌ Missing Base Case

❌ Wrong Base Case

❌ Not Moving Toward Base Case

Key Takeaways

Self-Calling

Base Case

Perfect For Trees

Call Stack

Pro Tip

Function Composition

Memoization

JavaScript Code Editor

Recursion

Recursion: A Function Calling Itself

Two Key Parts

Call Stack (Top to Bottom):

Iterative (Loop)

✅ Recursive

How Recursion Works

Classic Examples

Array and Object Recursion

Tree Traversal

Not Tail Recursive

✅ Tail Recursive

❌ Missing Base Case

❌ Wrong Base Case

❌ Not Moving Toward Base Case

Key Takeaways

Self-Calling

Base Case

Perfect For Trees

Call Stack

Pro Tip