科特林：尾递归的相互递归函数

假设我写这样的代码：科特林：尾递归的相互递归函数

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

我怎么科特林优化这些相互递归函数，这样我就可以不用在抛出StackOverflowError运行main？ tailrec关键字适用于单一函数递归，但没有更复杂的内容。我还看到一个警告，即在使用tailrec关键字的地方找不到尾部呼叫。对于编译器来说这可能太难了？

来源

2016-03-01 denine99

您可以将功能请求添加到https://youtrack.jetbrains.com以获得“互尾递归”功能，如果您希望将它添加到Kotlin中，那么这是最好的选择。如果它已经被请求或计划，那么还要首先在那里搜索。 –

我在这里创建了一个Kotlin问题：https://youtrack.jetbrains.com/issue/KT-11307 – denine99

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

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

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

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

来源

2017-06-19 08:54:54 comonad

很酷，听起来我们可以通过编写一个蹦床方法来支持JVM中的这个方法，该方法使用给定的参数调用方法引用。应该修改'even'和'odd'函数以返回方法引用加上下一个参数。我们通过调用trampoline方法并引用'even'函数和参数'99999'来进行第一次调用。 – denine99

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

尾部呼叫是作为一个程序的最后动作进行子程序调用。如果尾调用可能会导致相同的子程序被再次调用链后来被称为，子程序据说是尾递归

所以你的情况不会被定义为一个尾递归。这不是警告所说的。

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

来源

2016-03-01 05:58:33 voddan

在同一页（稍作编辑）：“功能性语言[如Kotlin]，目标是JVM [倾向于]实现直接[或自我]尾递归，但不是相互尾尾递归。“我可以向你保证，Haskell支持相互尾部递归。 –

它呢？凉！我认为是这样，只是因为它是Haskell，它会的。谢谢你的提示。 – voddan

你能否进一步澄清？在偶数/奇数的例子中，even和off的最终动作是一个子程序调用，我们看到在调用链中稍后调用相同的子程序。因此，通过定义，这两个函数都是尾递归的。 – denine99

这是@ comonad的trampoline suggestion的实现。有用！

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

来源

2017-06-22 09:12:06 denine99

酷！ :)有没有办法通过Runnable来做到这一点？ – comonad

科特林：尾递归的相互递归函数

回答

相关问题