在Java 8中实现无堆栈递归

Question

如何在Java中实现无堆栈递归？

似乎出现最多的词是"蹦床",我不知道这意味着什么.

有人在IN DETAIL中解释如何在Java中实现无堆栈递归吗？还有什么是"蹦床"？

如果你不能提供其中任何一个,你能指出我正确的方向(即一本书来阅读它或一些教导所有这些概念的教程)？

Answer 1

蹦床是一种将基于堆栈的递归转换为等效循环的模式.由于循环不添加堆栈帧,因此可以将其视为无堆栈递归的一种形式.

这是我发现有用的图表:

来自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<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()

笔记

• 拳击将使Java效率低下.
• 这段代码写在SO上; 它尚未经过测试甚至编译

进一步阅读

• Java Basics:Call如何工作
• 堆栈和递归消除
• 维基百科
• 在C#中跳跃蹦床 - 堆栈友好的递归
• 反蹦床
• 什么是蹦床功能？