Back to Main ACS Page

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:

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:

Simple Example: Factorial

// Recursive factorial function (Java) public static int factorial(int n) { if (n == 0 || n == 1) { return 1; } return n * factorial(n - 1); } // Example usage public static void main(String[] args) { System.out.println(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 (Java) public static int fibonacci(int n) { if (n <= 0) return 0; if (n==1) return 1; return fibonacci(n - 1) + fibonacci(n - 2); } // Example usage public static void main(String[] args) { System.out.println(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 (Java) public static long fibonacciMemo(int n, Map<Integer, Long> memo) { if (memo.containsKey(n)) return memo.get(n); if (n <= 0) return 0; if (n==1) return 1; long value=fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo); memo.put(n, value); return value; } // Example usage public static void main(String[] args) { Map<Integer, Long> memo=new HashMap<>(); System.out.println(fibonacciMemo(50, memo)); // Much faster for large inputs }
2. Linked List Recursion
// Node definition (Java) static class Node { int value; Node next; Node(int value) { this.value = value; this.next = null; } } // Find length of linked list recursively public static int getLength(Node head) { if (head == null) { return 0; } return 1 + getLength(head.next); } // Reverse a linked list recursively public static Node reverseList(Node head) { if (head == null || head.next == null) { return head; } Node newHead = reverseList(head.next); 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 public static int factorialRecursive(int n) { if (n == 0 || n == 1) return 1; return n * factorialRecursive(n - 1); } // Iterative public static int factorialIterative(int n) { int result = 1; for (int i = 2; i <= n; i++) result *=i; return result; }

Common Recursion Pitfalls

Techniques to Improve Recursive Solutions

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:

Recursive List Problems:

Tree Recursion: