在 Java 8 中实现无堆栈递归

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

下面是我发现有用的图表：

从 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;
}

这是怎么回事？我们采取了递归步骤，并使其成为循环内部的迭代。我们循环，直到我们完成所有递归步骤，将结果或每次迭代存储在变量中。

这更有效，因为将创建更少的帧。我们不是为每个递归调用（帧）存储一个帧，而是存储当前值和剩余的迭代次数（2个值）。n

这种模式的推广是蹦床。

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 基础知识：调用的工作原理
• 堆栈和递归消除
• 维基百科
• 在 C# 中跳跃蹦床 – 堆栈友好递归
• 反向蹦床
• 什么是蹦床功能？

来自维基百科：

蹦床是一个循环，它以迭代方式调用返回的函数

在自己对蹦床进行一些研究时，我偶然发现了上面的线。所以我做了一些关于 thunk 在 Java 中如何工作和/或看起来像什么的实验。我得到了一个令人满意的结果，值得分享。这是从上一个答案的升级，因为thunk看起来与递归函数非常相似。这是由于自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，你可以把它当成一个穷人的。在你自己的项目中，如果你愿意，你可以对函数使用多态性。任何一个都应该工作。PairTupelSupplier

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

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循环是蹦床。我们有一个调用 a 返回 ！while loopfunctionthunk