Kotlin:相互递归函数的尾递归

Question

假设我写这样的代码:

tailrec fun odd(n: Int): Boolean =
        if (n == 0) false
        else even(n - 1)

tailrec fun even(n: Int): Boolean =
        if (n == 0) true
        else odd(n - 1)

fun main(args:Array<String>) {
    // :( java.lang.StackOverflowError
    System.out.println(even(99999))
}

如何让Kotlin优化这些相互递归的函数,以便我可以在main不抛出StackOverflowError的情况下运行？该tailrec关键字适用于单函数递归,但没有更复杂的.我还看到一个警告,即在使用tailrec关键字的地方没有找到尾调用.也许这对编译器来说太难了？

Answer 1

您正在寻找的是“适当的尾调用”。JVM 不支持这些，所以你需要Trampolines。

适当的尾调用会在跳转（而不是调用）尾调用函数之前清理其自身函数（参数、局部变量）的内存。这样尾部被调用的函数就可以直接返回到它的调用者-调用者-函数。无限相互递归是可能的。（在函数式语言中，这是最重要的特性之一。）

为了在汇编程序中允许正确的尾调用，您需要一个命令来跳转（转到）到通过指针引用的例程/方法。OOP 需要调用（存储跳转回堆栈的位置，然后跳转）到通过指针引用的例程/方法。

您可以使用蹦床设计模式模拟正确的尾调用，也许通过库有一些支持。蹦床是一个while循环，它调用一个函数，该函数返回对下一个函数的引用，该函数返回对下一个函数的引用......