Стек Java и рекурсия

Question

Мой вопрос касается дизайна стека Java. Был ли он разработан с учетом рекурсии или рекурсия стала чем-то особенным из-за структуры стека?

Answer 1

Отдельный не ответ:

На самом деле, "реальная вещь" с рекурсией - это хвостовая рекурсия , и компиляторы признают это и под прикрытием оптимизируют ее в итерационные циклы.

И удивительно: вы не получите этого с Java.Таким образом, в реальном мире рекурсия и Java не сочетаются друг с другом.Всего несколько тысяч рекурсивных вызовов могут привести к сбою вашей JVM.Таким образом, вы абсолютно стараетесь избежать рекурсии в настоящей Java.Это изящная вещь для небольших разрозненных проблем.Но помимо этого, рекурсия - это «не» вещь в Java.

И дизайн стека, вероятно, больше основан на идее создания простой, легко портируемой системы для виртуальной машины 20 лет назад.И обе концепции (стеки и рекурсия) существовали задолго до выпуска Java v1.

Answer 2

Java8 добавил лямбда-выражение и функциональный интерфейс, как описано здесь: 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 = …

см. Более подробную информацию по этой ссылке: https://www.scala -exercises.org / scala_tutorial / tail_recursion