Module 3: Introduction to Recursion

Master the fundamentals of recursion. Learn how to implement and analyze recursive algorithms.

Module Objectives

Upon completion of this module, you will be able to:

Identify a recursive problem and determine when recursion is appropriate
Define a recursive solution by breaking down a problem into smaller, similar problems
Understand base cases and recursive cases in recursive functions
Trace recursive function calls to understand execution flow
Apply recursive solutions to linked list and tree problems
Analyze the time and space complexity of recursive algorithms

Recursion Basics

What is Recursion?

Recursion is a programming technique where a function calls itself to solve a problem. It's particularly useful for problems that can be broken down into smaller instances of the same problem.

Key Components of Recursion:

Base Case: A condition that stops the recursion
Recursive Case: The function calling itself with a smaller/simpler input
Progress Toward Base Case: Ensuring the recursion will eventually terminate

Simple Example: Factorial

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

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

Recursive Function Tracing

Understanding how recursive calls stack up is crucial:

// Tracing factorial(5):
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)))
      → 5 * (4 * (3 * 2))
    → 5 * (4 * 6)
  → 5 * 24
→ 120
  

More Recursive Examples

1. Fibonacci Sequence

// Recursive Fibonacci (inefficient but illustrative)
function fibonacci(n) {
  // Base cases
  if (n <= 0) return 0;
  if (n === 1) return 1;
  
  // Recursive case
  return fibonacci(n - 1) + fibonacci(n - 2);
}

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

Note: The simple recursive implementation of Fibonacci has exponential time complexity O(2^n). For efficiency, you'd use dynamic programming or memoization:

// Fibonacci with memoization
function fibonacciMemo(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 0) return 0;
  if (n === 1) return 1;
  
  memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
  return memo[n];
}

// Example usage
console.log(fibonacciMemo(50)); // Much faster for large inputs
  

2. Linked List Recursion

// Node definition
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

// Find length of linked list recursively
function getLength(head) {
  // Base case: empty list
  if (head === null) {
    return 0;
  }
  
  // Recursive case: count this node plus the rest
  return 1 + getLength(head.next);
}

// Reverse a linked list recursively
function reverseList(head) {
  // Base cases: empty list or only one node
  if (head === null || head.next === null) {
    return head;
  }
  
  // Recursive case
  const newHead = reverseList(head.next);
  
  // Reverse the pointers
  head.next.next = head;
  head.next = null;
  
  return newHead;
}
  

Recursion vs. Iteration

It's important to understand when to use recursion versus iterative approaches:

Aspect	Recursion	Iteration
Memory Usage	Uses call stack (higher memory overhead)	Typically uses less memory
Code Clarity	Often more elegant and readable for certain problems	May be more straightforward for simple problems
Performance	Can be slower due to function call overhead	Usually faster
Stack Overflow Risk	Possible with deep recursion	Not an issue
Best For	Tree traversals, divide-and-conquer algorithms	Simple loops, performance-critical code

Iterative vs. Recursive Factorial Example

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

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

Common Recursion Pitfalls

Missing Base Case: Leads to infinite recursion and stack overflow
Inefficient Overlapping Subproblems: Can make recursion exponentially slow
Stack Overflow: With deeply nested recursion
Unnecessary Recursion: When an iterative solution is simpler

Techniques to Improve Recursive Solutions

Memoization: Store results of subproblems to avoid redundant calculations
Tail Recursion: Special form where recursive call is the last operation
Trampolining: Technique to avoid stack overflow by simulating recursion

Practice with LeetCode Problems

Note: Previously, this course referenced the CodeSignal Arcade for practice, which is no longer available. The LeetCode problems below follow the same principles and are an excellent alternative for practicing recursion.

Basic Recursion Problems:

Fibonacci Number - Classic recursion example
Climbing Stairs - Similar to Fibonacci but with a practical context
Pow(x, n) - Implement power function using recursion

Recursive List Problems:

Reverse Linked List - Practice recursive linked list manipulation
Swap Nodes in Pairs - Intermediate linked list recursion
Merge Two Sorted Lists - Can be solved elegantly with recursion

Tree Recursion:

Maximum Depth of Binary Tree - Simple tree recursion
Same Tree - Compare two trees recursively
Path Sum - Find paths in a tree recursively