Avoiding Stackoverflow using recursion in Java (Tail Call Optimization)

One of the biggest concerning issue with recursion is ‘stack-overflow’ especially when dealing with large scale of data.

I always wondered what are the possible ways to solve stack-overflow caused by recursion?

There are concept like  Tail Call Optimization (TCO) to solve this issue, however that is not currently supported by Java (unlike languages like Elixir, Java script, Lua, Python, TCl, Kotlin etc).

Although simple TCO implementation in Java is not hard, One of which can be implemented by creating a chain of responsibilities to perform any computation as mentioned below:

Create first instance / responsibility to perform initial/first computation, then keep creating responsibilities until the desired result is not achieved.

In our implementation, creation of first instance is done with the first call to ‘createRecursionLikeCall’ from main, which will perform the first/initial computation on data and also responsible of creating a second instance to perform secondary computation. This process of computation and creation of further instances continue until the ‘End of Computation (EOC)’ conditions are met.

Once EOC (End of Computation) conditions are met then:

1.      Stop creating further instance (This is implemented by setting isDone to ‘true’)

2.      Return the result of entire computation (done by implementing ‘getValue’).

interface TailCallOptimizationInterface<T>

{

    default T getValue() {

        throw new RuntimeException("Not implemented");

    }

    default boolean isDone() {

        return false;

    }

    default TailCallOptimizationInterface<T> nextCall() {

        throw new IllegalStateException();

    }

    default T compute() {

        return Stream.iterate(this, TailCallOptimizationInterface::nextCall)

             .filter(TailCallOptimizationInterface::isDone)

             .findAny()

             .get()

             .getValue();

    }

}

public final class Factorial {

    public static TailCallOptimizationInterface<Integer>

                                   createRecursionLikeCall(int val, int fact)

    {

        if (val == 1 /* EOC condition for factorial */) {

            // End of Computation (EOC) conditions are met, hence we need to

            // stop creating further instances.

            return new TailCallOptimizationInterface<Integer>() {

                @Override

                public Integer getValue() {

                    return fact;

                }

                @Override

                public boolean isDone() {

                    return true;

                }

            };

        }

        return new TailCallOptimizationInterface<Integer>() {

            @Override

            public TailCallOptimizationInterface<Integer> nextCall() {

                // 1. Create another instance to perform secondary computation

                // on data.

                // 2. Manage secondary instance computation limit by changing

                // createRecursionLikeCall parameter values.

                return createRecursionLikeCall(val - 1, fact * val);

            }

        };

    }

    public static void main(String [] args) {

        int input = 10;

        System.out.println ("factorial of " + input + ":" +

              Factorial.createRecursionLikeCall(input, 1).compute());

    }

}

Note: While creating secondary instance in nextCall, we need to take care of initialise instance boundaries to define its computation scope, this can be handy when performing search operations of large datasets. 

Finally, I have used Java 8 as an example here, although similar implementation can be done in previous version of Java