重新审视使用 Groovy™ 计算斐波那契数列

作者： Paul King

发布时间：2022-09-08 10:59AM

在之前的文章中，我们探讨了在 Groovy 中使用矩阵，包括使用矩阵计算斐波那契数列。但是，计算斐波那契数列真的需要那么复杂吗？不，完全不需要。针对这种情况，你可以使用各种一行代码的解决方案（重复该文章中的计算）

Stream.iterate([1, 1], f -> [f[1], f.sum()]).limit(8).toList()*.head()

上一篇文章更多是关于使用矩阵，而非斐波那契本身，尽管希望学习到斐波那契矩阵是莱斯利矩阵的特例是一个额外的收获。

让我们来看看在 Groovy 中编写斐波那契方法的其他几种选择。

迭代式

除非你将函数式编程语言作为你的第一门语言学习，否则你可能在最初的编程学习练习中编写过迭代式的阶乘或斐波那契。斐波那契的这种算法可能看起来像这样

def fib(n) {
    if (n <= 1) return n

    def previous = n.valueOf(1), next = previous, sum
    (n-2).times {
        sum = previous
        previous = next
        next = sum + previous
    }
    next
}

assert fib(10) == 55
assert fib(50L) == 12586269025L
assert fib(100G) == 354224848179261915075G

这个解决方案唯一有趣的部分是动态惯用语的使用。我们没有为n提供明确的类型，因此“鸭子类型”意味着该方法适用于Integer、Long和BigInteger值。这个实现使用提供的n的类型进行所有计算，因此方法的调用者控制着这方面。

Groovy 提供了指定显式类型（如Number）的选项，或者如果你愿意，可以使用TypeChecked或CompileStatic进行类型推断。我们稍后会看到这些选项的示例。

递归式

一旦你掌握了迭代式编程，你的下一个编程学习练习可能就是阶乘或斐波那契的递归版本。对于斐波那契，你可能编写了这样的代码

def fib(n) {
    if (n <= 1) return n
    fib(n - 1) + fib(n - 2)
}

assert fib(10) == 55
assert fib(50L) == 12586269025L
assert fib(100G) == 354224848179261915075G

这个简单的版本效率极低。例如，调用 fib(6) 最终会计算 fib(2) 五次

Call tree for Fibonacci(6)

有几种方法可以避免这种重复。一个选项是使用@Memoized注解。在方法上添加此注解会导致编译器将适当的代码注入到方法中以缓存结果。这对于斐波那契等纯函数来说是理想的，因为它们对于给定的输入总是返回相同的输出。有注解属性可以调整此类缓存的大小，但这里不需要这种复杂性。

@Memoized
def fib(n) {
    if (n <= 1) return n
    fib(n - 1) + fib(n - 2)
}

assert fib(10) == 55
assert fib(50L) == 12586269025L
assert fib(100G) == 354224848179261915075G

现在它的运行速度与迭代方法一样快。如果你碰巧使用Closure而不是方法，你可以调用Closure上的一个memoize方法。

这种方法（实际上是通用递归）的一个问题是，对于较大的n值，你会遇到栈溢出异常，例如 `fib(500G)`。Groovy 通过包含`TailRecursive`注解来支持尾调用消除。在这种情况下，编译器会注入一个“展开的”非递归版本的算法。为了使“展开”成功，算法需要重新设计，以便在任何返回语句中最多只发生一次对 fib 的调用。以下是按这种方式重新设计的算法版本

@TailRecursive
static fib(n, a, b) {
    if (n == 0) return a
    if (n == 1) return b
    fib(n - 1, b, a + b)
}

assert fib(10, 0, 1) == 55
assert fib(50L, 0L, 1L) == 12586269025L
assert fib(100G, 0G, 1G) == 354224848179261915075G
assert fib(500G, 0G, 1G) == 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125G

如果你以前没有见过它，这比原始版本稍微复杂一点，但现在它既高效又可以处理大的n值。我们可以像这样静态编译以获得更快的速度

@TailRecursive
@CompileStatic
static fib(Number n, Number a, Number b) {
    if (n == 0) return a
    if (n == 1) return b
    fib(n - 1, b, a + b)
}

assert fib(10, 0, 1) == 55
assert fib(50L, 0L, 1L) == 12586269025L
assert fib(100G, 0G, 1G) == 354224848179261915075G
assert fib(500G, 0G, 1G) == 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125G

如果你正在使用Closure，你可以考虑使用Closure上的trampoline方法来达到类似的效果。

流式

我们在本博客文章的开头看到了基于流的“一行代码”解决方案。让我们采用我们目前使用的“鸭子类型”惯用法来定义一个 fib 方法。它可能看起来像这样

def fib(n) {
    def zero = n.valueOf(0)
    def one = n.valueOf(1)
    Stream.iterate([zero, one], t -> [t[1], t.sum()])
    .skip(n.longValue())
    .findFirst().get()[0]
}

assert fib(10) == 55
assert fib(50L) == 12586269025L
assert fib(100G) == 354224848179261915075G

字节码和 AST 转换

最后，只是为了让你了解所有选项，这里有一个使用@Bytecode AST 转换的版本，它允许你直接在 Groovy 中编写 JVM 字节码！请注意，这属于“永远不要这样做”的范畴，但为了让你知道你可以这样做，这里将其包含在内

@Bytecode
int fib(int i) {
    l0
    iload 1
    iconst_2
    if_icmpgt l1
    iconst_1
    _goto l2
    l1
    frame SAME
    aload 0
    iload 1
    iconst_2
    isub
    invokevirtual '.fib','(I)I'
    aload 0
    iload 1
    iconst_1
    isub
    invokevirtual '.fib', '(I)I'
    iadd
    l2
    frame same1,'I'
    ireturn
}

assert fib(10) == 55

在考虑将其用于极端情况之外的任何事情之前，请务必阅读该转换的注意事项。它更多是作为一种有趣的尝试，而不是任何人在生产环境中想要做的事情。

祝你编写自己的算法玩得开心！