Kotlin是否支持互递归？有无新特性或替代实现方案

截至2024年，Kotlin仍未原生支持嵌套函数的直接互递归定义——也就是你示例中那种先声明boo再声明foo，boo里引用未声明的foo会报“未解析引用”的问题，根源是Kotlin的嵌套函数遵循顺序依赖规则，未提前声明的函数无法被引用。官方也没有推出专门支持互递归的装饰器或语法特性，但可以通过以下变通方法实现互递归：

方法1：使用延迟初始化的函数变量 #

这是最常用的实现方式，先声明函数类型的lateinit变量，再分别赋值实现互相引用：

import java.util.Deque

fun match(xs: Deque<*>): Boolean {
    lateinit var boo: (Deque<*>) -> Boolean
    lateinit var foo: (Deque<*>) -> Boolean

    boo = { deque ->
        // 这里写boo的业务逻辑，比如判断队列状态后调用foo
        if (deque.isEmpty()) true else foo(deque)
    }

    foo = { deque ->
        // 这里写foo的业务逻辑，比如处理队列元素后调用boo
        val element = deque.poll()
        boo(deque)
    }

    return boo(xs)
}

方法2：使用接口/抽象类封装 #

通过定义包含互递归函数的接口，再用匿名对象实现，利用接口成员函数可互相引用的特性：

import java.util.Deque

fun match(xs: Deque<*>): Boolean {
    interface RecursiveMatcher {
        fun boo(xs: Deque<*>): Boolean
        fun foo(xs: Deque<*>): Boolean
    }

    val matcher = object : RecursiveMatcher {
        override fun boo(xs: Deque<*>): Boolean {
            // boo的逻辑实现
            return if (xs.size % 2 == 0) foo(xs) else false
        }

        override fun foo(xs: Deque<*>): Boolean {
            // foo的逻辑实现
            xs.poll()
            return boo(xs)
        }
    }

    return matcher.boo(xs)
}

关于尾递归优化的说明 #

需要注意：Kotlin的tailrec注解仅支持单一函数的尾递归优化，互递归场景无法享受编译器的尾递归栈优化，如果递归深度较大，仍可能出现栈溢出问题，需结合其他手段（比如手动迭代）规避。

内容的提问来源于stack exchange，提问作者Adrian