在Java 8中实现无堆栈递归 [英] Achieving Stackless recursion in Java 8
问题描述
如何在Java中实现无叠加递归？
How do I achieve stackless recursion in Java?
似乎出现最多的词是蹦床，我不知道这意味着什么。
The word that seems to come up the most is "trampolining", and I have no clue what that means.
有人 IN DETAIL 可以解释如何在Java中实现无堆栈递归吗？还有什么是蹦床？
Could someone IN DETAIL explain how to achieve stackless recursion in Java? Also, what is "trampolining"?
如果你不能提供其中任何一个，请你指出我正确的方向（即一本书来阅读它或一些教导所有这些概念的教程） ）？
If you cannot provide either of those, could you please point me in the right direction (i.e., a book to read about it or some tutorial that teaches all of these concepts)?
推荐答案
蹦床是一种将基于堆栈的递归转换为等效循环的模式。由于循环不添加堆栈帧，因此可以将其视为无堆栈递归的一种形式。
A trampoline is a pattern for turning stack-based recursion into an equivalent loop. Since loops don't add stack frames, this can be thought of as a form of stackless recursion.
这是我发现有用的图表：
Here's a diagram I found helpful:
您可以将蹦床视为一个起始值的过程;迭代该值;然后以最终值退出。
考虑这种基于堆栈的递归：
Consider this stack-based recursion:
public static int factorial(final int n) {
if (n <= 1) {
return 1;
}
return n * factorial(n - 1);
}
对于每次递归调用，都会推送一个新帧。这是因为如果没有新帧的结果，则不能评估先前帧。当堆栈变得太深而内存不足时，这将成为一个问题。
For every recursive call this makes, a new frame is pushed. This is because the prior frame cannot evaluate without the result of the new frame. This will become a problem when the stack gets too deep and we run out of memory.
幸运的是，我们可以将此功能表达为循环：
Luckily, we can express this function as a loop:
public static int factorial2(int n) {
int i = 1;
while (n > 1) {
i = i * n;
n--;
}
return i;
}
这里发生了什么？我们采取递归步骤并使其成为循环内的迭代。我们循环，直到我们完成所有递归步骤，将结果或每次迭代存储在变量中。
What's going on here? We've taken the recursive step and made it the iteration inside of a loop. We loop until we have completed all recursive steps, storing the result or each iteration in a variable.
由于创建的帧数较少，因此效率更高。我们不存储每个递归调用的帧（ n 帧），而是存储当前值和剩余的迭代次数（2个值）。
This is more efficient since fewer frames will be created. Instead of storing a frame for each recursive call (n frames), we store the current value and the number of iterations remaining (2 values).
这种模式的概括是蹦床。
The generalization of this pattern is a trampoline.
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 需要两名成员：
- 当前步骤的值;
- 下一个要计算的函数，如果我们已经到达最后一步，则没有任何内容
任何可以用这种方式描述的计算可以是蹦床。
Any computation that can be described in this way can be "trampolined".
这对于factorial来说是什么样的？
What does this look like for factorial?
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()
注释
- < a href =https://docs.oracle.com/javase/tutorial/java/data/autoboxing.html\"rel =noreferrer>拳击将使Java效率低下。
- 此代码是用SO编写的;它尚未经过测试甚至编译
- Boxing will make this inefficient in Java.
- This code was written on SO; it has not been tested or even compiled
进一步阅读
- Java Basics: How Call Works
- Stacks and Recursion Elimination
- Wikipedia
- Jumping the Trampoline in C# – Stack-Friendly Recursion
- Reverse Trampoline
- What is a trampoline function?
这篇关于在Java 8中实现无堆栈递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
