The Java stack and recursion

Question

My question is about the design of the Java stack. Was it designed with recursion in mind, or did recursion become a thing due to the structure of the stack?

Answer 1

A distinct non-answer:

Actually, the "real thing" with recursion is tail recursion, and compilers recognising that, and under the cover optimising it into iterative loops.

And surprise: you don't get that with Java. Thus, in the real world, recursion and Java do not go together nicely. Just a few thousand recursive calls might crash your JVM. So you absolutely try to avoid recursion in real java. It is a neat thing for small isolated problems. But beyond that, recursion is "not" a thing in Java.

And the design of the stack is probably more based on the idea to create a simple, easy to port system for a virtual machine 20 years ago. And both concepts (stacks, and recursion) both existed long before Java v1 was released.

Answer 2

Java8 added lambda expression and functional interface as described here: https://blog.knoldus.com/tail-recursion-in-java-8/

which allows us to define our own tail recursive interface:

@FunctionalInterface
public interface TailCall {
    TailCall apply();
    default boolean isComplete() {
        return false;
    }
    default T result() {
        throw new Error("not implemented");
    }
    default T invoke() {
        return Stream.iterate(this, TailCall::apply)
                .filter(TailCall::isComplete)
                .findFirst()
                .get()
                .result();
    }
}

therefore you can do sth like this:

public class Factorial{
    public static TailCall factorialTailRec(final int factorial, final int number) {
        if (number == 1)
            return TailCalls.done(factorial);
        else
            return call(() -> factorialTailRec(factorial * number, number - 1));
    }
}

however, Java natively does not have any tail recursive optimization in mind. as comparison to Scala(better Java, I think), Scala has @tailrec annotation, therefore compiler will optimize the recursion into non-recursive manner when this hint is provided and given that function is a true tailrec function.

@tailrec
def gcd(a: Int, b: Int): Int = …

please see more detailed info in this link: https://www.scala-exercises.org/scala_tutorial/tail_recursion