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优化这些相互递归的函数，以便在不抛出StackOverflower错误的情况下运行main？tailrec关键字适用于单函数递归，但没有更复杂的功能。我还看到一个警告，在使用关键字tailrec的地方没有找到尾部调用。也许这对编译器来说太难了？

Answer 1

以下是@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))
}

Answer 2

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

尾部调用是作为过程的最终操作执行的子例程调用。如果尾部调用可能导致同一子例程稍后在调用链中再次调用，则该子例程称为尾部递归

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

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

Answer 3

您正在寻找的是“正确的尾调用”。JVM不支持这些，所以您需要蹦床。

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

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

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