Module 3: Introduction to Recursion
Master the fundamentals of recursion.
Learn how to implement and analyze recursive algorithms.
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 (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:
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; }
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.