Java 堆栈和递归

Question

我的问题是关于 Java 堆栈的设计。它是在设计时考虑了递归，还是由于堆栈的结构而导致递归？

Answer 1

一个明显的非答案：

实际上，带递归的 "real thing" 是 tail recursion，编译器认识到这一点，并在幕后将其优化为迭代循环。

令人惊讶的是：Java 无法做到这一点。因此，在现实世界中，递归和 Java 并不能很好地结合在一起。几千次递归调用可能会使您的 JVM 崩溃。所以你绝对要尽量避免真正的递归java。对于孤立的小问题来说，这是一件很巧妙的事情。但除此之外，递归是 "not" Java.

中的一件事

而stack的设计大概更多的是基于20年前为虚拟机打造一个简单易移植系统的想法。这两个概念（堆栈和递归）在 Java v1 发布之前就已经存在。

Answer 2

Java8 添加了 lambda 表达式和功能接口，如下所述：https://blog.knoldus.com/tail-recursion-in-java-8/

它允许我们定义自己的尾递归接口：

@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();
    }
}

因此你可以这样做：

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));
    }
}

然而，Java 本身并没有考虑任何尾递归优化。与 Scala 相比（我认为更好 Java），Scala 具有 @tailrec 注释，因此当提供此提示并假定该函数是真正的 tailrec 函数时，编译器会将递归优化为非递归方式.

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

请在link中查看更多详细信息：https://www.scala-exercises.org/scala_tutorial/tail_recursion

Java 堆栈和递归

The Java stack and recursion

java

recursion

stack

history

design-patterns