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

假设我写这样的代码：

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关键字的地方找不到tail-calls。 编译器也许这太难了？

Answer 1

你在找什么是“正确的尾巴呼叫”。 JVM不支持这些，所以你需要蹦床 。

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

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

你可以用蹦床的设计模式模拟适当的尾巴呼叫，也许有一些通过图书馆的支持。 蹦床是一个while循环，调用一个函数，返回一个引用到下一个函数，它返回一个引用到下一个…

Answer 2

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

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

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

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

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)) }