Java 中的弹跳模式：掌握不发生堆栈溢出的递归

约 3 分钟

也称为

弹跳
尾调用优化

弹跳设计模式的意图

Java 中的弹跳模式通过将递归函数调用转换为迭代循环来优化递归函数调用，从而避免堆栈溢出错误。

弹跳模式的详细解释以及现实世界中的示例

现实世界中的示例

想象一下，你在组织接力赛。每位跑步者将接力棒传递给下一位跑步者，直到比赛结束。但是，如果每位跑步者都必须实际跑回起点将接力棒传递给下一位跑步者，那么比赛将会效率低下且容易出错。相反，跑步者将接力棒直接传递给排队的下一位跑步者，他们会无缝地继续比赛。
编程中的弹跳模式的工作原理类似，它通过确保每个递归步骤都能有效地传递，而不必返回到起点，从而防止堆栈溢出（就像我们的跑步者永远不必回溯一样）。

通俗易懂地说

Java 中的弹跳模式允许在不耗尽堆栈内存的情况下有效地进行递归，从而优化深度递归调用，以提高性能和堆栈安全性。

维基百科上说

在 Java 中，弹跳指的是使用反射来避免使用内部类，例如在事件监听器中。反射调用的时间开销可以用来换取内部类的空间开销。Java 中的弹跳通常涉及创建通用的监听器来将事件传递给外部类。

Java 中弹跳模式的编程示例

以下是 Java 中的 Trampoline 实现。

当在返回的 Trampoline 上调用 get 时，它会在内部迭代调用返回的 Trampoline 上的 jump，只要返回的具体实例是 Trampoline，直到返回的实例是 done 时才会停止。

public interface Trampoline<T> {

  T get();

  default Trampoline<T> jump() {
    return this;
  }

  default T result() {
    return get();
  }

  default boolean complete() {
    return true;
  }

  static <T> Trampoline<T> done(final T result) {
    return () -> result;
  }

  static <T> Trampoline<T> more(final Trampoline<Trampoline<T>> trampoline) {
    return new Trampoline<T>() {
      @Override
      public boolean complete() {
        return false;
      }

      @Override
      public Trampoline<T> jump() {
        return trampoline.result();
      }

      @Override
      public T get() {
        return trampoline(this);
      }

      T trampoline(final Trampoline<T> trampoline) {
        return Stream.iterate(trampoline, Trampoline::jump)
            .filter(Trampoline::complete)
            .findFirst()
            .map(Trampoline::result)
            .orElseThrow();
      }
    };
  }
}

使用 Trampoline 获取斐波那契数列的值。

@Slf4j
public class TrampolineApp {

    public static void main(String[] args) {
        LOGGER.info("Start calculating war casualties");
        var result = loop(10, 1).result();
        LOGGER.info("The number of orcs perished in the war: {}", result);

    }

    public static Trampoline<Integer> loop(int times, int prod) {
        if (times == 0) {
            return Trampoline.done(prod);
        } else {
            return Trampoline.more(() -> loop(times - 1, prod * times));
        }
    }
}

程序输出

19:22:24.462 [main] INFO com.iluwatar.trampoline.TrampolineApp - Start calculating war casualties
19:22:24.472 [main] INFO com.iluwatar.trampoline.TrampolineApp - The number of orcs perished in the war: 3628800

何时在 Java 中使用弹跳模式

使用弹跳模式的情况

处理使用大量递归且有发生堆栈溢出错误风险的算法时。
当 Java 语言本身不支持尾调用优化时。

弹跳模式 Java 教程

Java 中弹跳模式的现实世界应用

实现需要深度递归的算法，例如某些树遍历、组合算法和数学计算。
需要尾调用优化以提高性能和堆栈安全性的函数式编程库和框架。
cyclops-react

弹跳模式的优缺点

优点

通过将深度递归转换为迭代来防止堆栈溢出。
通过避免深度递归调用的开销来提高性能。
通过使递归调用看起来像一系列步骤来简化代码。

权衡

在理解和实现弹跳机制方面可能会引入额外的复杂性。
需要将自然递归算法转换为继续传递风格。

迭代器：这两种模式都旨在将潜在的递归操作转换为迭代过程，但迭代器模式更通用。
状态：与弹跳一样，状态模式也可以处理复杂的狀態转换，这些转换有时会涉及类似递归的狀態变化。
策略：这种模式在定义算法系列（或弹跳情况下的延续）方面可以关联，并使它们可以互换。