334

Take a look at the following two methods:

public static void foo() {
    try {
        foo();
    } finally {
        foo();
    }
}

public static void bar() {
    bar();
}

Running bar() clearly results in a StackOverflowError, but running foo() does not (the program just seems to run indefinitely). Why is that?

10
  • 17
    Formally, the program will eventually stop because errors thrown during the processing of the finally clause will propagate to the next level up. But don't hold your breath; the number of steps taken will be about 2 to the (maximum stack depth) and the throwing of exceptions isn't exactly cheap either. Sep 15, 2012 at 16:41
  • 3
    It would be "correct" for bar(), though.
    – dan04
    Sep 15, 2012 at 16:47
  • 6
    @dan04: Java doesn't do TCO, IIRC to ensure having full stack traces, and for something related to reflection (probably having to do with stack traces as well).
    – ninjalj
    Sep 15, 2012 at 16:47
  • 4
    Interestingly enough when I tried this out on .Net (using Mono), the program crashed with a StackOverflow error without ever calling finally.
    – Kibbee
    Sep 15, 2012 at 18:55
  • 11
    This is about the worst piece of code I ever saw :)
    – poitroae
    Sep 16, 2012 at 9:49

6 Answers 6

333

It doesn't run forever. Each stack overflow causes the code to move to the finally block. The problem is that it will take a really, really long time. The order of time is O(2^N) where N is the maximum stack depth.

Imagine the maximum depth is 5

foo() calls
    foo() calls
       foo() calls
           foo() calls
              foo() which fails to call foo()
           finally calls
              foo() which fails to call foo()
       finally
           foo() calls
              foo() which fails to call foo()
           finally calls
              foo() which fails to call foo()
    finally calls
       foo() calls
           foo() calls
              foo() which fails to call foo()
           finally calls
              foo() which fails to call foo()
       finally
           foo() calls
              foo() which fails to call foo()
           finally calls
              foo() which fails to call foo()
finally calls
    foo() calls
       foo() calls
           foo() calls
              foo() which fails to call foo()
           finally calls
              foo() which fails to call foo()
       finally
           foo() calls
              foo() which fails to call foo()
           finally calls
              foo() which fails to call foo()
    finally calls
       foo() calls
           foo() calls
              foo() which fails to call foo()
           finally calls
              foo() which fails to call foo()
       finally
           foo() calls
              foo() which fails to call foo()
           finally calls
              foo() which fails to call foo()

To work each level into the finally block take twice as long an the stack depth could be 10,000 or more. If you can make 10,000,000 calls per second, this will take 10^3003 seconds or longer than the age of the universe.

11
  • 4
    Nice, even if I try to make the stack as small as possible via -Xss, I get a depth of [150 - 210], so 2^n ends up being a [47 - 65] digits number. Not going to wait that long, that is near enough to infinity for me.
    – ninjalj
    Sep 15, 2012 at 17:05
  • 64
    @oldrinb Just for you, I increased the depth to 5. ;) Sep 15, 2012 at 17:18
  • 4
    So, at the end of the day when foo finally does terminate, it will result in a StackOverflowError?
    – arshajii
    Sep 15, 2012 at 21:29
  • 5
    following the math, yup. the last stack overflow from the last finally which failed to stack overflow will exit with... stack overflow =P. couldn't resist.
    – WhozCraig
    Sep 15, 2012 at 23:13
  • 1
    So does this actually mean even that try catch code also should end up in stackoverflow error??
    – LPD
    Jan 4, 2013 at 13:33
40

When you get an exception from the invocation of foo() inside the try, you call foo() from finally and start recursing again. When that causes another exception, you'll call foo() from another inner finally(), and so on almost ad infinitum.

3
  • 5
    Presumably, a StackOverflowError (SOE) is sent when there is no more space on the stack to call new methods. How can foo() be called from finally after a SOE?
    – assylias
    Sep 15, 2012 at 16:02
  • 4
    @assylias: if there's not enough space, you will return from the latest foo() invocation, and invoke foo() in the finally block of your current foo() invocation.
    – ninjalj
    Sep 15, 2012 at 16:10
  • +1 to ninjalj. You will not call foo from anywhere once you cannot call foo due to the overflow condition. this includes from the finally block, which is why this will, eventually (age of the universe) terminate.
    – WhozCraig
    Sep 16, 2012 at 6:00
38

Try running the following code:

    try {
        throw new Exception("TEST!");
    } finally {
        System.out.println("Finally");
    }

You will find that the finally block executes before throwing an Exception up to the level above it. (Output:

Finally

Exception in thread "main" java.lang.Exception: TEST! at test.main(test.java:6)

This makes sense, as finally is called right before exiting the method. This means, however, that once you get that first StackOverflowError, it will try to throw it, but the finally must execute first, so it runs foo() again, which gets another stack overflow, and as such runs finally again. This keeps happening forever, so the exception is never actually printed.

In your bar method however, as soon as the exception occurs, it is just thrown straight up to the level above, and will be printed

1
26

In effort to provide reasonable evidence that this WILL eventually terminate, I offer the following rather meaningless code. Note: Java is NOT my language, by any stretch of the most vivid imagination. I proffer this up only to support Peter's answer, which is the correct answer to the question.

This attempts to simulate the conditions of what happens when an invoke can NOT happen because it would introduce a stack overflow. It seems to me the hardest thing people are failing to grasp in that the invoke does not happen when it cannot happen.

public class Main
{
    public static void main(String[] args)
    {
        try
        {   // invoke foo() with a simulated call depth
            Main.foo(1,5);
        }
        catch(Exception ex)
        {
            System.out.println(ex.toString());
        }
    }

    public static void foo(int n, int limit) throws Exception
    {
        try
        {   // simulate a depth limited call stack
            System.out.println(n + " - Try");
            if (n < limit)
                foo(n+1,limit);
            else
                throw new Exception("StackOverflow@try("+n+")");
        }
        finally
        {
            System.out.println(n + " - Finally");
            if (n < limit)
                foo(n+1,limit);
            else
                throw new Exception("StackOverflow@finally("+n+")");
        }
    }
}

The output of this little pointless pile of goo is the following, and the actual exception caught may come as a surprise; Oh, and 32 try-calls (2^5), which is entirely expected:

1 - Try
2 - Try
3 - Try
4 - Try
5 - Try
5 - Finally
4 - Finally
5 - Try
5 - Finally
3 - Finally
4 - Try
5 - Try
5 - Finally
4 - Finally
5 - Try
5 - Finally
2 - Finally
3 - Try
4 - Try
5 - Try
5 - Finally
4 - Finally
5 - Try
5 - Finally
3 - Finally
4 - Try
5 - Try
5 - Finally
4 - Finally
5 - Try
5 - Finally
1 - Finally
2 - Try
3 - Try
4 - Try
5 - Try
5 - Finally
4 - Finally
5 - Try
5 - Finally
3 - Finally
4 - Try
5 - Try
5 - Finally
4 - Finally
5 - Try
5 - Finally
2 - Finally
3 - Try
4 - Try
5 - Try
5 - Finally
4 - Finally
5 - Try
5 - Finally
3 - Finally
4 - Try
5 - Try
5 - Finally
4 - Finally
5 - Try
5 - Finally
java.lang.Exception: StackOverflow@finally(5)
23

Learn to trace your program:

public static void foo(int x) {
    System.out.println("foo " + x);
    try {
        foo(x+1);
    } 
    finally {
        System.out.println("Finally " + x);
        foo(x+1);
    }
}

This is the output I see:

[...]
foo 3439
foo 3440
foo 3441
foo 3442
foo 3443
foo 3444
Finally 3443
foo 3444
Finally 3442
foo 3443
foo 3444
Finally 3443
foo 3444
Finally 3441
foo 3442
foo 3443
foo 3444
[...]

As you can see the StackOverFlow is thrown at some layers above, so you can do additional recursion steps till you hit another exception, and so on. This is an infinite "loop".

4
  • 11
    it's not actually infinite loop, if you're patient enough it will eventually terminate. I won't hold my breath for it though.
    – Lie Ryan
    Sep 15, 2012 at 17:19
  • 4
    I would posit that it is infinite. Each time it reaches the maximum stack depth it throws an exception and unwinds the stack. However in the finally it calls Foo again causing it to again reuse the stack space it has just recovered. It will go back and forth throwing exceptions and then going back Dow the stack until it happens again. Forever.
    – Kibbee
    Sep 15, 2012 at 18:24
  • Also, you'll want that first system.out.println to be in the try statement, otherwise it will unwind the loop further than it should. possibly causing it to halt.
    – Kibbee
    Sep 15, 2012 at 18:38
  • 1
    @Kibbee The problem with your argument is that when it calls foo the second time, in the finally block, it is no longer in a try. So while it will go back down the stack and create more stack overflows once, the second time it will just rethrow the error produced by the second call to foo, instead of re-deepening.
    – amalloy
    Aug 20, 2015 at 2:48
1

The program merely seems to run forever; it actually terminates, but it takes exponentially more time the more stack space you have. To prove that it finishes, I wrote a program that first depletes most of the available stack space, and then calls foo, and finally writes a trace of what happened:

foo 1
  foo 2
    foo 3
    Finally 3
  Finally 2
    foo 3
    Finally 3
Finally 1
  foo 2
    foo 3
    Finally 3
  Finally 2
    foo 3
    Finally 3
Exception in thread "main" java.lang.StackOverflowError
    at Main.foo(Main.java:39)
    at Main.foo(Main.java:45)
    at Main.foo(Main.java:45)
    at Main.foo(Main.java:45)
    at Main.consumeAlmostAllStack(Main.java:26)
    at Main.consumeAlmostAllStack(Main.java:21)
    at Main.consumeAlmostAllStack(Main.java:21)
    ...

The code:

import java.util.Arrays;
import java.util.Collections;
public class Main {
  static int[] orderOfOperations = new int[2048];
  static int operationsCount = 0;
  static StackOverflowError fooKiller;
  static Error wontReachHere = new Error("Won't reach here");
  static RuntimeException done = new RuntimeException();
  public static void main(String[] args) {
    try {
      consumeAlmostAllStack();
    } catch (RuntimeException e) {
      if (e != done) throw wontReachHere;
      printResults();
      throw fooKiller;
    }
    throw wontReachHere;
  }
  public static int consumeAlmostAllStack() {
    try {
      int stackDepthRemaining = consumeAlmostAllStack();
      if (stackDepthRemaining < 9) {
        return stackDepthRemaining + 1;
      } else {
        try {
          foo(1);
          throw wontReachHere;
        } catch (StackOverflowError e) {
          fooKiller = e;
          throw done; //not enough stack space to construct a new exception
        }
      }
    } catch (StackOverflowError e) {
      return 0;
    }
  }
  public static void foo(int depth) {
    //System.out.println("foo " + depth); Not enough stack space to do this...
    orderOfOperations[operationsCount++] = depth;
    try {
      foo(depth + 1);
    } finally {
      //System.out.println("Finally " + depth);
      orderOfOperations[operationsCount++] = -depth;
      foo(depth + 1);
    }
    throw wontReachHere;
  }
  public static String indent(int depth) {
    return String.join("", Collections.nCopies(depth, "  "));
  }
  public static void printResults() {
    Arrays.stream(orderOfOperations, 0, operationsCount).forEach(depth -> {
      if (depth > 0) {
        System.out.println(indent(depth - 1) + "foo " + depth);
      } else {
        System.out.println(indent(-depth - 1) + "Finally " + -depth);
      }
    });
  }
}

You can try it online! (Some runs might call foo more or fewer times than others)

Not the answer you're looking for? Browse other questions tagged or ask your own question.