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.WhosebugError
    System.out.println(even(99999))
}

如何让 Kotlin 优化这些相互递归的函数，这样我就可以运行 main 而不会抛出 WhosebugError？ tailrec 关键字适用于单函数递归，但没有比这更复杂的了。我还看到一条警告，指出在使用 tailrec 关键字的地方找不到尾调用。也许这对编译器来说太难了？

Answer 1

来自维基百科 https://en.wikipedia.org/wiki/Tail_call :

a tail call is a subroutine call performed as the final action of a procedure. If a tail call might lead to the same subroutine being called again later in the call chain, the subroutine is said to be tail-recursive

所以你的情况根据定义不是尾递归。警告不是这么说的。

目前编译器无法优化它，主要是因为这种情况非常罕见。 ~~但我不确定 Haskel 是否会优化它。~~

Answer 2

您要找的是"proper tail calls"。 JVM 不支持这些，所以你需要 trampolines.

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

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

您可以使用 trampoline 设计模式模拟适当的尾部调用，也许库提供了一些支持。蹦床是一个 while 循环，它调用一个函数，该函数 return 是对下一个函数的引用，该函数 return 是对下一个...

的引用

Answer 3

这是@comonad 的一个实现。有效！

import kotlin.reflect.KFunction

typealias Result = Pair<KFunction<*>?, Any?>
typealias Func = KFunction<Result>

tailrec fun trampoline(f: Func, arg: Any?): Any? {
    val (f2,arg2) = f.call(arg)
    @Suppress("UNCHECKED_CAST")
    return if (f2 == null) arg2 
        else trampoline(f2 as Func, arg2)
}

fun odd(n: Int): Result =
        if (n == 0) null to false
        else ::even to n-1

fun even(n: Int): Result =
        if (n == 0) null to true
        else ::odd to n-1

fun main(args:Array<String>) {
    System.out.println(trampoline(::even, 9999999))
}

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

Kotlin: Tail recursion for mutually recursive functions

recursion

tail-recursion

kotlin