在 Java 8 中实现 Stackless 递归

Question

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

似乎出现最多的词是"trampolining"，我不知道那是什么意思。

有人可以详细解释如何在Java中实现无堆栈递归吗？另外，什么是"trampolining"？

如果您不能提供其中任何一个，能否请您为我指明正确的方向（即，一本可以阅读的书或一些教授所有这些概念的教程）？

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

备注

Boxing 会使 Java.
这段代码写在SO上；它没有经过测试甚至编译

进一步阅读

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?

Answer 2

来自Wikipedia：

a trampoline is a loop that iteratively invokes thunk-returning functions

在自己研究蹦床时，我无意中发现了上面这行。所以我做了一些关于 thunk will work and or look like in Java. And I got a satisfying result that is worth sharing. It is quite an upgrade from the previous answer since a thunk looks very similar to the recursive function. This is due to the functional interfaces 自 java 8.

以来如何添加的实验

// Recursive
private int factorial(final int number) {
    return (number == 1)
        ? 1 
        : number * factorial(number -1);
}

将执行阶乘的递归方式（上面）与下面的 thunk 返回版本进行比较。注意到相似之处了吗？

// The thunk returning version
private Pair<Supplier, Long> factorial(long number, long sum){
    return (number == 1)
        ? new Pair<>(null, sum)
        : new Pair<>(() -> factorial(number -1, sum * number), null);
}

我这里用的是Java的Pair，你可以当成穷人的Tupel。在您自己的项目中，如果您愿意，可以在 Supplier 函数上使用多态性。两者都应该有效。

要调用 thunk 返回版本，我使用下面的 while 循环。

private long trampoline(long number) {
    Pair<Supplier, Long> supplierOrResult = new Pair<>(()-> factorial(number, 1), null);

    while (supplierOrResult.getValue() == null) {
        supplierOrResult = (Pair<Supplier, Long>)supplierOrResult.getKey().get();
    }

    return supplierOrResult.getValue();
}

当你回顾维基百科的引用时，你会发现这里的 while 循环就是蹦床。我们有一个 while loop 调用 function 那个 returns 一个 thunk!

在 Java 8 中实现 Stackless 递归

Achieving Stackless recursion in Java 8

java

stack-overflow

recursion

tail-call-optimization