The quickest escape from recursion in Java

Question

Is there a way to cleanly and quickly escape from recursion in Java? There is a way to break out from a for loop by using the break; statement. Is there an equivalent pattern or method of escaping a recursion?

I can think of spawning a separate thread, and once the value is computed, simply killing a thread rather than bubbling up the recursion stack. Is there a better way?

There is already a question that discusses how you can break out of recursion: here.

What I am looking for is a quicker way of achieving it, possibly without going back through the stack. Something like a goto or a break statement.

The criteria considered here are:

• The ease of refactoring to use this escape
• The raw performance (the faster the better)
• The length in practice (the quicker to write/add the better)

The answer that I am looking for will explain both the performance and simplicity of a solution- this is asked in the context of an algorithmic competition, so solutions that require less refactoring are prefered.

Why would I want to use it?

Sometimes when coding for some algorithmic competition, you need to return a value from inside a recursion and I wonder if you can do it faster, by using this kind of break. Think about algorithm that looks like:

public static MyClass myFunct(MyClass c, int x){
    myFunct(c, c.valueA);
    myFunct(c, c.valueB);
    //do some work - that modifies class c
    if(c.valueE == 7){
        //finished work, can return without unwinding the whole recursion
        //No more modifications to class c
    }
    myFunct(c, c.valueC);
    myFunct(c, c.valueD);
    return c;
}

Answer 1

In general the simplest approach to this problem would be to simply replace the recursion with a non-recursive solution. This would aswell most likely improve the performance if implemented properly. The approach with killing the thread is rather ugly - i'd highly recommend not to use this. But there's no way to break out of a recursion without rewinding the stack.

Recursion:

int rec(int i){
    if(i == condition)
         return i;

    //do some stuff with i

    return rec(i);
}

Non-recursive:

int nonrec(int i){
    Stack<Integer> stack = new Stack<>();
    stack.push(i);

    while(!stack.isEmpty())
    {
        Integer v = stack.pop();

        //same as above, but no bubbling through the stack
        if(v == condition)
            return v;

        //do some stuff with v

        stack.push(v);
    }

    //undefined, the algorithm hasn't found a solution
    return -1;
}

This is a rather simple example, but the principle is the same for more complex recursive problems.

Answer 2

The answer to your question is quite simple:

Just do it the usual way, i.e., unwinding the stack yourself with returns. Why? Because this is not as slow as you might think. Unless the computation in your recursion is highly trivial and the stack depth is very very high, the returning will never influence the runtime of your algorithm noticeably.

Basically, you have the following options:

• If possible, transform your algorithm to an iterative one.
• Transform your algorithm to be end recursive and hope that the VM will reuse the stack frame. Then, returning out of recursion is virtually equal to one simple return.
• Throw an exception. However, this will be even slower than returning, because the stack trace has to be built, which ultimatly traverses the stack, too. Also the stack has to be unwound to check for catches. You win nothing.

The former two options are viable, but not always possible. But honestly, don't think about it. Returning out of a deep stack is not the part that makes your algorithm slow. If you have an algorithm with a very deep recursion, then you have a problem anyway (stack overflow, costs of the recursive calls) and should consider to rewrite your algorithm. If the stack depth is low, then this is a non-issue anyway.

Here is a simple Java test program to show you what I mean:

import java.io.ByteArrayOutputStream;
import java.io.PrintStream;

public class DeepRecursion {

    private long returnStartTime;

    public int recurse(int i) {
        int r = (int)Math.sqrt((double)i); // Some non-trivial computation
        if(i == 0) {
            returnStartTime = System.currentTimeMillis();
            return r;
        }
        return r + recurse(i-1);
    }

    public void testRecursion(int i, PrintStream p) {
        long startTime = System.currentTimeMillis();
        int result = recurse(i);
        long endTime = System.currentTimeMillis();

        p.println(
                "Recursion depth: " + i + " Result: " + result + "\n" +
                "Time for recursion" + (returnStartTime - startTime) + "\n" +
                "Time for return " + (endTime - returnStartTime) + "\n"
                );
    }

    public void testIteration(int i, PrintStream p) {
        long startTime = System.currentTimeMillis();
        int result = 0;
        for(int k = 0; k <= i; k++) {
            int r = (int)Math.sqrt((double)k); // Some non-trivial computation
            result += r;
        }
        long endTime = System.currentTimeMillis();
        p.println("Iteration length: " + i + " Result: " + result + "\nTime: " + (endTime - startTime) );
    }

    public static void main(String[] args) {
        DeepRecursion r = new DeepRecursion();
        PrintStream nullStream = new PrintStream(new ByteArrayOutputStream());

        for(int k = 0; k < 10; k++) {
            // Test stack depths from 1024 to 33554432
            for(int i = 10; i < 26; i++) {
                r.testIteration(1 << i, k == 9 ? System.out : nullStream);
                r.testRecursion(1 << i, k == 9 ? System.out : nullStream);
            }
        }
    }
}

It computes a recursive function which will have a stack depth equal to the input parameter. The function computes a square root in each stack fram e to simulate some non-trivial computation. It also computes the same function in an iterative way. To warm up the JIT, the program is first executed 9 times without printing the result; only the tenth result is printed. Here are my results (I had to increase the stack size to 1 gigabyte with -Xss1g. Here are the results from my machine:

Iteration length: 1024 Result: 21360
Time for iteration: 0
Recursion depth: 1024 Result: 21360
Time for recursion 0
Time for return 0

Iteration length: 2048 Result: 60810
Time for iteration: 0
Recursion depth: 2048 Result: 60810
Time for recursion 0
Time for return 0

Iteration length: 4096 Result: 172768
Time for iteration: 0
Recursion depth: 4096 Result: 172768
Time for recursion 0
Time for return 0

Iteration length: 8192 Result: 490305
Time for iteration: 0
Recursion depth: 8192 Result: 490305
Time for recursion 0
Time for return 0

Iteration length: 16384 Result: 1390016
Time for iteration: 0
Recursion depth: 16384 Result: 1390016
Time for recursion 0
Time for return 0

Iteration length: 32768 Result: 3938198
Time for iteration: 0
Recursion depth: 32768 Result: 3938198
Time for recursion 0
Time for return 0

Iteration length: 65536 Result: 11152256
Time for iteration: 0
Recursion depth: 65536 Result: 11152256
Time for recursion 1
Time for return 0

Iteration length: 131072 Result: 31570201
Time for iteration: 0
Recursion depth: 131072 Result: 31570201
Time for recursion 1
Time for return 0

Iteration length: 262144 Result: 89347840
Time for iteration: 2
Recursion depth: 262144 Result: 89347840
Time for recursion 1
Time for return 1

Iteration length: 524288 Result: 252821886
Time for iteration: 2
Recursion depth: 524288 Result: 252821886
Time for recursion 4
Time for return 1

Iteration length: 1048576 Result: 715304448
Time for iteration: 5
Recursion depth: 1048576 Result: 715304448
Time for recursion 7
Time for return 3

Iteration length: 2097152 Result: 2023619820
Time for iteration: 9
Recursion depth: 2097152 Result: 2023619820
Time for recursion 14
Time for return 4

Iteration length: 4194304 Result: 1429560320
Time for iteration: 18
Recursion depth: 4194304 Result: 1429560320
Time for recursion 29
Time for return 12

Iteration length: 8388608 Result: -986724456
Time for iteration: 36
Recursion depth: 8388608 Result: -986724456
Time for recursion 56
Time for return 28

Iteration length: 16777216 Result: -1440040960
Time for iteration: 72
Recursion depth: 16777216 Result: -1440040960
Time for recursion 112
Time for return 61

Iteration length: 33554432 Result: 712898096
Time for iteration: 145
Recursion depth: 33554432 Result: 712898096
Time for recursion 223
Time for return 123

As you see, it takes 3 millisecond to return from a stack of depth one million. Larger stack sizes cause longer times, possibly due to the stack no longer fitting into L3 cache. However, if you need such large stacks, you have a problem anyway, as described above. Running Java with 1 gigabyte max stack size is not the best idea. Any stack size below 131072 is not even measurable in milliseconds. In a sane algorithm, the stack should be much smaller than this, so you should always be fine.

As you see, the fastest solution is the iterative one, so if a very deep recursion is too slow, avoid it completely instead of only skipping the return.

Conclusion

If recursion is too slow for you, get rid of it completely. Just skipping the return won't make a big difference.

Answer 3

Say you have some inner, repeated recursion, like this not-so-sensible code:

public A f(B b) {
    C c = new C();
    return recf(b, c);
}

private A recf(B b, C c) {
    ...
    A a = recf(b2, c2);
    if (a != null) { // found
        return a;
    }
    ...
    return recf(b3, c3);
}

This will yield a sequence of returns when found (a != null).

The analogy to break is a Throwable.

public A f(B b) {
    C c = new C();
    try (
        recf(b, c);
        return null; // not found
    } catch (ResultFoundException<A> e) {
        return e.getResult();
    }
}

private void recf(B b, C c) throws ResultFoundException<A> {
    ...
}

public class ResultFoundException<A> implements RuntimeException {
    ...

    /** Speed-up thanks to James_pic. */
    @Override
    public Throwable fillInStackTrace() { }
}

Answer 4

If you change your algorithm to maintain its own stack rather than using the system CPU stack you can just discard the stack.

Answer 5

As it was pointed out by other people, the stack must be rewinded.

Having another thread is ugly and probably way slower than than throwing an exception.

I would try to find a non-recursive approach or do normal recursion with proper returns. Maybe if you give an example of what your are trying to do people can point you into the right direction.

If I needed to do this desperately, I would have a wrapper method that catches the exception thrown by the recursive function.

Disclaimer: I haven't tried this so it may not even compile :)

class GotAResultException extends Exception {
  private Object theResult;
  public GotAResultException(Object theResult) {
    this.theResult = theResult;
  }
  public Object getResult() {
    return theResult;
  }
}

Object wrapperMethod(Object blaParameters) {
  try {
    recursiveMethod(blaParameters);
  } catch (GotAResultException e) {
    return e.getResult();
  }
  // maybe return null if no exception was thrown?
  // Your call
  return null;
}

void recursiveMethod(Object blaParameters) throws GotAResultException {
  // lots of magical code
  // that calls recursiveMethod recursivelly
  // ...
  // And then we found the solution!
  throw new GotAResultException("this is the result");
}

Answer 6

A widely well accepted design - even it might depend on your particular circumstances - is using the Java Future<T> (or similar). If you are about to use threads, bear in mind that thread cancellation requires a safe and clean policy. There's a very good literature about these subjects, e.g. Java Concurrency In Practice.

Answer 7

One option is to set a flag on MyClass and return based on that:

public static MyClass myFunct(MyClass c, int x){
    if (c.isDoneCalculating) {
        return c;
    }
    myFunct(c, c.valueA);
    myFunct(c, c.valueB);
    //do some work - that modifies class c
    if(c.valueE == 7){
        c.isDoneCalculating = true;
        //finished work, can return without unwinding the whole recursion
        //No more modifications to class c
    }
    myFunct(c, c.valueC);
    myFunct(c, c.valueD);
    return c;
}