recursion - 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 需要调用(存储要跳回堆栈的位置，然后跳转)到通过指针引用的例程/方法。

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