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。 编译器也许这太难了?

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

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

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

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

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

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

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

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

    这里是@ 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)) }