Recursive Problem Solving & the Call Stack

1. What is Recursion?

At its heart, recursion is the process of a method calling itself to solve a progressively smaller version of the same problem. Instead of using a loop to iterate towards a solution, a recursive method breaks the problem down into a smaller piece it can solve now and a sub-problem it delegates to another call to itself.

For this to work without running forever, every recursive method must have two essential components:

1. A base case: The simplest version of the problem, for which the answer is known and can be returned directly without making another recursive call. This is the stopping condition.
2. A recursive case: The part of the method that breaks the problem down and calls itself with a simpler or smaller input, moving it one step closer to the base case.

To build your intuition, let's start with a video from freeCodeCamp.org that uses an excellent analogy of people waiting in a line to explain this idea of breaking down a problem and having a stopping condition.

2. How Recursion Works: The Call Stack

The "magic" of recursion is made possible by a fundamental mechanism in program execution: the call stack. Every time a method is called in your Java program, the Java Virtual Machine (JVM) pushes a stack frame onto the call stack. This frame contains the method's parameters, its local variables, and the address to return to when it finishes.

When a method calls another method, a new frame is pushed on top. When a method returns, its frame is popped off, and execution resumes in the frame below it.

In recursion, the method keeps calling itself, so it continuously pushes new frames for itself onto the stack. This continues until a base case is reached. At that point, the chain of calls stops, and the methods start returning one by one, popping their frames off the stack. This process of returning is often called the "unwinding" of the stack.

The freeCodeCamp.org video provides another great analogy to visualize this.

For a more formal, text-based explanation, the following article provides a concise and clear breakdown of the call stack.

3. Example 1: Calculating a Factorial

The factorial function is the quintessential example of recursion. The factorial of a non-negative integer $n$, denoted as $n!$, is the product of all positive integers up to $n$. For example, $5!=5\times 4\times 3\times 2\times 1=120$.

Notice the self-referential pattern: $5!=5\times 4!$, and more generally, $n!=n\times (n-1)!$. This structure is perfect for recursion.

• Recursive Case: factorial(n) is n * factorial(n - 1).
• Base Case: We need a point to stop. By definition, $1!=1$ and $0!=1$. So, if $n\le 1$, we can just return 1.

Here is the implementation in Java:

public class Factorial {
    public static long factorial(int n) {
        // Base Case: The stopping condition
        if (n <= 1) {
            return 1;
        }
        // Recursive Case: The function calls itself with a smaller problem
        else {
            return n * factorial(n - 1);
        }
    }

    public static void main(String[] args) {
        int number = 5;
        System.out.println("Factorial of " + number + " is " + factorial(number)); // Output: 120
    }
}

Let's trace factorial(5):

1. factorial(5) calls factorial(4) and waits.
2. factorial(4) calls factorial(3) and waits.
3. factorial(3) calls factorial(2) and waits.
4. factorial(2) calls factorial(1) and waits.
5. factorial(1) hits the base case and returns 1.
6. factorial(2) receives 1, calculates 2 * 1, and returns 2.
7. factorial(3) receives 2, calculates 3 * 2, and returns 6.
8. factorial(4) receives 6, calculates 4 * 6, and returns 24.
9. factorial(5) receives 24, calculates 5 * 24, and returns 120.

The following images perfectly illustrate this process. The first shows the flow of calls and returns, while the second shows the state of the call stack at each step.

4. Example 2: Reversing a String

String reversal is another problem that can be solved elegantly with recursion. Let's think about how to break it down.

The reverse of "hello" is "olleh". We can express this as the reverse of "ello" ("olle") followed by "h".
So, reverse("hello") = reverse("ello") + "h".

• Recursive Case: reverse(someString) is reverse(all_but_the_first_character) + first_character.
• Base Case: If the string is empty or has only one character, its reverse is itself.

The following video demonstrates this logic and provides an excellent animation of the call stack during the process.

Here's the corresponding Java code, which you can see matches the logic from the video.

public class StringReverser {
    public static String reverse(String str) {
        // Base Case
        if (str == null || str.length() <= 1) {
            return str;
        }
        // Recursive Case
        return reverse(str.substring(1)) + str.charAt(0);
    }

    public static void main(String[] args) {
        String original = "hello";
        System.out.println("Reverse of '" + original + "' is '" + reverse(original) + "'"); // Output: 'olleh'
    }
}

Notice how the work (+ str.charAt(0)) happens after the recursive call. This means the concatenation happens during the "unwinding" phase of the stack, which is what produces the reversed order.

5. A Framework for Recursive Thinking

When you encounter a new problem, it can be tricky to see the recursive solution. Here is a step-by-step framework to guide your thinking. Adopting this mindset is key to mastering recursion.

6. Your Turn: A Practical Exercise

Now it's time to apply what you've learned. Your task is to write a recursive method to find the sum of all the digits in a non-negative integer.

For example, sumDigits(123) should return 1 + 2 + 3 = 6.

Recursive thinking:

• How can you break down sumDigits(123)? It could be 3 + sumDigits(12).
• The Java operators / 10 (integer division) and % 10 (modulo) will be very helpful here.
• What is the base case? What's the simplest input you can have?

Use the following skeleton code and complete the sumDigits method.

public class DigitSum {

    public static int sumDigits(int n) {
        // Your implementation here
        // 1. What is the base case?
        
        // 2. What is the recursive step?
        //    Hint: Use n % 10 to get the last digit.
        //    Hint: Use n / 10 to get the rest of the number.
        
        return 0; // Placeholder
    }

    public static void main(String[] args) {
        int number = 123;
        System.out.println("Sum of digits for " + number + " is: " + sumDigits(number)); // Expected: 6

        int number2 = 9876;
        System.out.println("Sum of digits for " + number2 + " is: " + sumDigits(number2)); // Expected: 30
        
        int number3 = 5;
        System.out.println("Sum of digits for " + number3 + " is: " + sumDigits(number3)); // Expected: 5
    }
}

public class DigitSum {

    public static int sumDigits(int n) {
        // Base case: If the number is a single digit, return itself.
        if (n < 10) {
            return n;
        }
        
        // Recursive step: The last digit + the sum of the rest of the digits.
        return (n % 10) + sumDigits(n / 10);
    }

    public static void main(String[] args) {
        int number = 123;
        System.out.println("Sum of digits for " + number + " is: " + sumDigits(number)); // Expected: 6

        int number2 = 9876;
        System.out.println("Sum of digits for " + number2 + " is: " + sumDigits(number2)); // Expected: 30
        
        int number3 = 5;
        System.out.println("Sum of digits for " + number3 + " is: " + sumDigits(number3)); // Expected: 5
    }
}

Conclusion

In this lesson, you took a significant first step into the world of recursive problem-solving. You've established a foundational understanding that will be critical for the more complex data structures and algorithms ahead.

Key Takeaways:

• Recursion is a method of solving problems where a function calls itself with a smaller version of the input.
• Every recursive function must have a base case to stop the recursion and a recursive case to move towards the base case.
• The call stack is the mechanism that manages recursive calls. Each call adds a frame to the stack, and frames are popped off as they return.
• If a base case is missing or never reached, the call stack will run out of memory, causing a java.lang.StackOverflowError.
• You can solve recursive problems by identifying the smallest possible input (base case) and figuring out how to express a larger problem in terms of a slightly smaller one (recursive case).

In our next lesson, we will use these foundational skills to implement our first data structure from scratch: a singly linked list. You will see how recursion provides a natural way to perform operations like traversal and manipulation on linked data.