用 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方法来实现类似的结果。

流

我们在本文开头看到了基于 Stream 的“单行代码”解决方案。让我们采用到目前为止使用过的鸭子类型特性，并定义一个 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

在考虑使用该转换进行任何除了极端情况之外的操作之前，请阅读该转换的注意事项。它更像是用来尝试的有趣的事情，而不是任何人在生产环境中想要做的事情。

祝你编写自己的算法愉快！