17.2. Infinite Recursion

If a recursive definition doesn’t have a base case or the recursive case doesn’t move towards and eventually reach a base case, then there is no way to terminate the recursive path.

  • This is called infinite recursion.

  • This problem is similar to an infinite loop – with the definition itself causing the infinite “looping”.

  • The biggest difference is that an infinite recursion is guaranteed to cause a stack overflow error.

Let’s try some code! Compile and run the following on Odin:

public class InfRecursion {
    public static void main(String[] args) {
       recurse();
    } // main

    public static void recurse() {
       recurse();
    }
} // InfRecursion

Eventually, the program will throw a StackOverflowError because it runs out of memory (stack space). You should see an error that looks something like the following:

Exception in thread "main" java.lang.StackOverflowError
at InfRecursion.recurse(InfRecursion.java:8)
at InfRecursion.recurse(InfRecursion.java:8)
at InfRecursion.recurse(InfRecursion.java:8)
...

Each call to recurse (called infinitely) sets up a new execution environment (stack frame), with new parameters and local variables. Each stack frame takes up memory in a special region called the stack. When a method returns, the memory taken up in the stack is freed up for other stack frames to use. In the situation above, recurse never returns. In fact, it keeps calling itself and each call adds another stack frame causing the stack to eventually fill up (overflow). When the stack fills up due to too many (unreturned) method calls, you get a StackOverflowError.

ASIDE: You may have noticed that StackOverflowError is reported as an exception but it does not have Exception in its name. Indeed, it is reported the same as exceptions because it is a sub-class of java.lang.Throwable, however, it is NOT a sub-class of java.lang.Exception. Instead, it is a sub-class of java.lang.Error, a class whose children comprise what the Java Virtual Machine considers to be errors that are non-recoverable during runtime.