在Java 8中实现无堆栈递归
如何在Java中实现无堆栈递归？
似乎最常出现的词是“蹦床”，我不知道这意味着什么。
有人在IN DETAIL中解释如何在Java中实现无堆栈递归吗？ 还有什么是“蹦床”？
如果你不能提供其中任何一个，你能指出我正确的方向（即一本书来阅读它或一些教导所有这些概念的教程）？
蹦床是一种将基于堆栈的递归转换为等效循环的模式。 由于循环不添加堆栈帧，因此可以将其视为无堆栈递归的一种forms。
这是我发现有用的图表：
来自bartdesmet.net
您可以将蹦床视为一个起始值的过程; 迭代该值; 然后以最终值退出。
考虑这个基于堆栈的递归：
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 { public T getValue() { throw new RuntimeException("Not implemented"); } public Optional> nextTrampoline() { return Optional.empty(); } public final T compute() { Trampoline trampoline = this; while (trampoline.nextTrampoline().isPresent()) { trampoline = trampoline.nextTrampoline().get(); } return trampoline.getValue(); } }
Trampoline需要两名成员：
- 当前步骤的价值;
- 下一个要计算的函数，如果我们已经到达最后一步，则没有任何内容
可以用这种方式描述的任何计算都可以“蹦床”。
这对于阶乘来说是什么样的？
public final class Factorial { public static Trampoline createTrampoline(final int n, final int sum) { if (n == 1) { return new Trampoline () { public Integer getValue() { return sum; } }; } return new Trampoline () { public Optional> nextTrampoline() { return Optional.of(createTrampoline(n - 1, sum * n)); } }; } }
并致电：
Factorial.createTrampoline(4, 1).compute()
笔记
- 拳击将使Java效率低下。
- 这段代码写在SO上; 它尚未经过测试甚至编译
进一步阅读
- Java Basics：Call如何工作
- 堆栈和递归消除
- 维基百科
- 在C＃中跳跃蹦床 - 堆栈友好递归
- 反蹦床
- 什么是蹦床function？