← Back to All Patterns

Recursion Pattern

🎯 Explain Like I'm 5...

Imagine you have a big task: clean your entire toy room! 🧸

🧒 Kid's Way (No Recursion): Try to clean everything at once - you get confused and don't know where to start! 😵

🧙 Smart Way (Recursion): Break it down into smaller tasks:

  • • Clean one toy →
  • • Now you have a SMALLER room to clean
  • • Keep doing this until room is clean! 🎉

🚀 Why is it powerful? Recursion lets you solve BIG problems by solving SMALL versions of the same problem! It's like using a magic trick where you make the problem smaller each time until it's easy to solve. Think of it like a Russian nesting doll - you open one doll to find a smaller one inside!

🎨 See It In Action!

Below you'll find interactive animations for each example. Use the controls to play, pause, and step through each algorithm!

▶ Play/Pause
⏭ Step Forward
🔄 Reset

When Should You Use This Pattern?

  • ✓You're working with trees or graphs (naturally recursive structures)
  • ✓The problem can be divided into smaller identical subproblems
  • ✓Mathematical problems with self-similar patterns
  • ✓You need to generate all possibilities

📝 Example 1: Calculate Factorial

Factorial of n (written as n!) means: n × (n-1) × (n-2) × ... × 1. For example, 5! = 5 × 4 × 3 × 2 × 1 = 120

Step-by-Step Thinking:

  1. Base case: If n is 0 or 1, return 1 (stopping condition!)
  2. Recursive case: n! = n × (n-1)!
  3. Each call makes the problem smaller: 5! → 4! → 3! → 2! → 1!
  4. Then multiply results back up: 1 → 2 → 6 → 24 → 120 ✓

Factorial(5) - Recursive Call Stack

📚 Call Stack (Diving Down):
factorial(5)
📞 Calling: Start: Calculate factorial(5)
Step 1 of 10Speed: 1500ms
Normal
Example 1: Factorial in Java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Recursion {
    // Calculate factorial using recursion
    // Example: factorial(5) = 5 * 4 * 3 * 2 * 1 = 120
    public static int factorial(int 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);
    }
    public static void main(String[] args) {
        System.out.println("Factorial of 5: " + factorial(5));  // 120
        System.out.println("Factorial of 0: " + factorial(0));  // 1
        System.out.println("Factorial of 7: " + factorial(7));  // 5040
    }
}
/*
 * How it works for factorial(5):
 * factorial(5) = 5 * factorial(4)
 * factorial(4) = 4 * factorial(3)
 * factorial(3) = 3 * factorial(2)
 * factorial(2) = 2 * factorial(1)
 * factorial(1) = 1 (base case!)
 *
 * Then multiply back up:
 * factorial(2) = 2 * 1 = 2
 * factorial(3) = 3 * 2 = 6
 * factorial(4) = 4 * 6 = 24
 * factorial(5) = 5 * 24 = 120
 */

📝 Example 2: Fibonacci Sequence

The Fibonacci sequence is: 0, 1, 1, 2, 3, 5, 8, 13... Each number is the sum of the previous two!

Step-by-Step Thinking:

  1. Base cases: fib(0) = 0, fib(1) = 1
  2. Recursive case: fib(n) = fib(n-1) + fib(n-2)
  3. To find fib(5), we need fib(4) and fib(3)
  4. This creates a tree of recursive calls that eventually reaches base cases

Fibonacci(5) - Recursion Tree

📚 Call Stack (Diving Down):
fib(5)
📞 Calling: Start: Calculate fib(5)
Step 1 of 13Speed: 1500ms
Normal
Example 2: Fibonacci in Java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class Fibonacci {
    // Calculate nth Fibonacci number using recursion
    // Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21...
    public static int fibonacci(int n) {
        // Base cases
        if (n == 0) return 0;
        if (n == 1) return 1;
        // Recursive case: fib(n) = fib(n-1) + fib(n-2)
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
    // Optimized version with memoization
    public static int fibonacciMemo(int n, int[] memo) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        // Check if already calculated
        if (memo[n] != -1) {
            return memo[n];
        }
        // Calculate and store in memo
        memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
        return memo[n];
    }
    public static void main(String[] args) {
        System.out.println("Fibonacci of 6: " + fibonacci(6));  // 8
        System.out.println("Fibonacci of 10: " + fibonacci(10)); // 55
        // Using memoization for better performance
        int n = 10;
        int[] memo = new int[n + 1];
        for (int i = 0; i <= n; i++) memo[i] = -1;
        System.out.println("Fibonacci of 10 (memo): " + fibonacciMemo(10, memo)); // 55
    }
}
/*
 * Recursion tree for fibonacci(5):
 *                    fib(5)
 *                  /        \
 *            fib(4)          fib(3)
 *           /      \        /      \
 *      fib(3)    fib(2)  fib(2)   fib(1)
 *      /   \     /   \   /   \
 *  fib(2) fib(1) f(1) f(0) f(1) f(0)
 *  /   \
 * f(1) f(0)
 *
 * Notice: Without memoization, we calculate fib(3) twice, fib(2) three times!
 * Time complexity: O(2^n) without memo, O(n) with memo
 */

📝 Example 3: Sum of Array Elements

Find the sum of all numbers in an array: [1, 2, 3, 4, 5]

Step-by-Step Thinking:

  1. Base case: Empty array returns 0
  2. Recursive case: first element + sum(rest of array)
  3. sum([1,2,3,4,5]) = 1 + sum([2,3,4,5])
  4. = 1 + 2 + sum([3,4,5]) = 1 + 2 + 3 + sum([4,5]) = ... = 15 ✓
Example 3: Sum Array in Java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class ArraySum {
    // Sum all elements in array using recursion
    public static int sumArray(int[] arr, int index) {
        // Base case: reached end of array
        if (index >= arr.length) {
            return 0;
        }
        // Recursive case: current element + sum of rest
        return arr[index] + sumArray(arr, index + 1);
    }
    // Alternative: working backwards from the end
    public static int sumArrayBackwards(int[] arr, int index) {
        // Base case: before start of array
        if (index < 0) {
            return 0;
        }
        // Recursive case
        return arr[index] + sumArrayBackwards(arr, index - 1);
    }
    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 5};
        System.out.println("Sum (forwards): " + sumArray(numbers, 0));  // 15
        System.out.println("Sum (backwards): " + sumArrayBackwards(numbers, numbers.length - 1));  // 15
    }
}
/*
 * How sumArray works for [1, 2, 3, 4, 5]:
 * sumArray([1,2,3,4,5], 0) = 1 + sumArray([...], 1)
 * sumArray([1,2,3,4,5], 1) = 2 + sumArray([...], 2)
 * sumArray([1,2,3,4,5], 2) = 3 + sumArray([...], 3)
 * sumArray([1,2,3,4,5], 3) = 4 + sumArray([...], 4)
 * sumArray([1,2,3,4,5], 4) = 5 + sumArray([...], 5)
 * sumArray([1,2,3,4,5], 5) = 0 (base case)
 *
 * Then add back up: 5 + 4 + 3 + 2 + 1 = 15
 */
Example 4: Power Function in Java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
public class Power {
    // Calculate x^n using recursion
    public static int power(int x, int n) {
        // Base case: anything to power 0 is 1
        if (n == 0) {
            return 1;
        }
        // Recursive case: x^n = x * x^(n-1)
        return x * power(x, n - 1);
    }
    // Optimized version using divide and conquer
    // x^n = (x^(n/2))^2 if n is even
    // x^n = x * (x^(n/2))^2 if n is odd
    public static int powerOptimized(int x, int n) {
        // Base case
        if (n == 0) return 1;
        // Calculate half power
        int halfPower = powerOptimized(x, n / 2);
        // If n is even: x^n = (x^(n/2))^2
        if (n % 2 == 0) {
            return halfPower * halfPower;
        }
        // If n is odd: x^n = x * (x^(n/2))^2
        else {
            return x * halfPower * halfPower;
        }
    }
    public static void main(String[] args) {
        System.out.println("2^5 = " + power(2, 5));  // 32
        System.out.println("3^4 = " + power(3, 4));  // 81
        System.out.println("5^0 = " + power(5, 0));  // 1
        System.out.println("2^10 (optimized) = " + powerOptimized(2, 10));  // 1024
    }
}
/*
 * Regular power(2, 5):
 * power(2, 5) = 2 * power(2, 4)
 * power(2, 4) = 2 * power(2, 3)
 * power(2, 3) = 2 * power(2, 2)
 * power(2, 2) = 2 * power(2, 1)
 * power(2, 1) = 2 * power(2, 0)
 * power(2, 0) = 1
 * Result: 2 * 2 * 2 * 2 * 2 = 32
 * Time: O(n)
 *
 * Optimized powerOptimized(2, 5):
 * power(2, 5) = 2 * power(2, 2)^2
 * power(2, 2) = power(2, 1)^2
 * power(2, 1) = 2 * power(2, 0)^2
 * power(2, 0) = 1
 * Time: O(log n) - much faster!
 */

🔑 Key Points to Remember

  • →Every recursion needs a BASE CASE (stopping condition) or it will run forever!
  • →Each recursive call should make the problem SMALLER
  • →Recursion uses the call stack - each call waits for the next to finish
  • →Can be more elegant than loops, but may use more memory (stack space)
  • →Time complexity varies: O(n) for linear, O(2^n) for tree-like recursion

💡 Pro Tips

  • 💡Always identify the base case first - that's your exit strategy!
  • 💡Draw the recursion tree to understand how calls branch and merge
  • 💡Consider using memoization to avoid recalculating the same values
  • 💡Some recursive solutions can be converted to iterative (using loops) for better memory efficiency

💪 Practice Problems

  • •Power of a Number (x^n)
  • •Reverse a String
  • •Binary Tree Traversals (Preorder, Inorder, Postorder)
  • •Tower of Hanoi
  • •Generate All Subsets
  • •Sum of Digits