Как достичь рекурсии без стекол в Java?
Слово, которое, кажется, больше всего подходит, "батут", и я не знаю, что это значит.
Может ли кто-нибудь в деталях объяснить, как добиться рекурсии без стекол в Java? Кроме того, что такое "батут"?
Если вы не можете предоставить ни один из них, не могли бы вы указать мне в правильном направлении (т.е. книгу, чтобы прочитать об этом или какой-то учебник, который учит всем этим понятиям)?
Батут - это шаблон для превращения основанной на стеке рекурсии в эквивалентную петлю. Поскольку циклы не добавляют стековые фреймы, это можно рассматривать как форму рекурсии без стеков.
Вот диаграмма, которую я нашел полезной:
Вы можете думать о батуте как о процессе, который принимает начальное значение; перебирает это значение; и затем выходит с окончательным значением.
Рассмотрим рекурсию на основе стека:
public static int factorial(final int n) {
if (n <= 1) {
return 1;
}
return n * factorial(n - 1);
}
Для каждого рекурсивного вызова, который это делает, помещается новый кадр. Это потому, что предыдущий кадр не может быть оценен без результата нового кадра. Это станет проблемой, когда стек становится слишком глубоким, и у нас заканчивается память.
К счастью, мы можем выразить эту функцию как цикл:
public static int factorial2(int n) {
int i = 1;
while (n > 1) {
i = i * n;
n--;
}
return i;
}
Что здесь происходит? Мы сделали рекурсивный шаг и сделали его итерацией внутри цикла. Мы выполняем цикл до тех пор, пока не выполним все рекурсивные шаги, сохраняя результат или каждую итерацию в переменной.
Это более эффективно, поскольку будет создано меньше кадров. Вместо сохранения кадра для каждого рекурсивного вызова (кадры n) мы сохраняем текущее значение и количество оставшихся итераций (2 значения).
Обобщением этого паттерна является батут.
public class Trampoline<T>
{
public T getValue() {
throw new RuntimeException("Not implemented");
}
public Optional<Trampoline<T>> nextTrampoline() {
return Optional.empty();
}
public final T compute() {
Trampoline<T> trampoline = this;
while (trampoline.nextTrampoline().isPresent()) {
trampoline = trampoline.nextTrampoline().get();
}
return trampoline.getValue();
}
}
Trampoline требует двух членов:
Любое вычисление, которое можно описать таким образом, может быть "трамплинировано".
Как это выглядит для факториала?
public final class Factorial
{
public static Trampoline<Integer> createTrampoline(final int n, final int sum)
{
if (n == 1) {
return new Trampoline<Integer>() {
public Integer getValue() { return sum; }
};
}
return new Trampoline<Integer>() {
public Optional<Trampoline<Integer>> nextTrampoline() {
return Optional.of(createTrampoline(n - 1, sum * n));
}
};
}
}
И позвонить:
Factorial.createTrampoline(4, 1).compute()
Примечания
Дальнейшее чтение