深度递归 DeepRecursiveFunction

源：Kotlin standard library - DeepRecursiveFunction

在处理深度未知的树状结构（如大型 JSON 解析、文件系统遍历、图算法）时，传统的基于调用栈（Call Stack）的递归函数很容易遇到 StackOverflowError。Kotlin 标准库提供的 DeepRecursiveFunction 是解决此类问题的终极武器。

核心问题：栈溢出

JVM 的线程栈大小是有限的（通常默认为 1MB 左右）。当递归深度达到几千层时，栈内存就会耗尽。

// 危险的普通递归
fun depth(node: Node?): Int {
    if (node == null) return 0
    // 每一层调用都会占用栈帧
    return maxOf(depth(node.left), depth(node.right)) + 1
}

解决方案：堆内存递归

DeepRecursiveFunction 通过在堆内存 (Heap) 中维护递归状态，绕过了线程栈的大小限制。只要堆内存足够（通常是 GB 级别），递归就可以无限进行。

基础语法

DeepRecursiveFunction 定义了一个带有 DeepRecursiveScope 接收者的 Lambda。在这个作用域中，你必须使用 callRecursive 代替直接的函数调用。

import kotlin.DeepRecursiveFunction

class Node(val left: Node?, val right: Node?)

// 定义函数：<参数类型, 返回类型>
val depth = DeepRecursiveFunction<Node?, Int> { node ->
    if (node == null) 0 else {
        // ⭐️ 关键：使用 callRecursive 进行递归调用
        val l = callRecursive(node.left)
        val r = callRecursive(node.right)
        maxOf(l, r) + 1
    }
}

// 调用方式与普通函数类似
val result = depth(rootNode)
// 或者使用 invoke
val result2 = depth.invoke(rootNode)

工作原理

DeepRecursiveFunction 的底层实现非常巧妙，它利用了 Kotlin 协程（Coroutines）的基础设施。

1. 它定义了一个 suspend 函数块。
2. callRecursive 实际上是一个挂起操作（suspension point）。
3. 当调用 callRecursive 时，当前的执行状态（Continuation）被保存到堆对象中，而不是推入线程栈。
4. 这本质上是将递归转换为了一个状态机循环。

为什么不需要 suspend 关键字？

虽然底层使用了协程机制，但 DeepRecursiveFunction 对外暴露的是同步 API。它在内部运行了一个微型的事件循环来驱动这个状态机，因此调用者不需要在协程作用域中，也不需要将函数标记为 suspend。

实战场景

场景一：深层目录遍历

文件系统可能存在极深的目录嵌套，或者符号链接导致的循环（需额外处理环检测）。

import java.io.File

val listFiles = DeepRecursiveFunction<File, List<File>> { dir ->
    val files = dir.listFiles() ?: return@DeepRecursiveFunction emptyList()
    val result = mutableListOf<File>()
    
    for (file in files) {
        if (file.isDirectory) {
            // 递归调用
            result.addAll(callRecursive(file))
        } else {
            result.add(file)
        }
    }
    result
}

场景二：复杂图算法

在处理算法题或图数据结构时，DFS（深度优先搜索）是最常用的算法。对于稀疏但极深的有向图，普通 DFS 必死无疑。

// 计算斐波那契数列（虽然通常用迭代，这里仅作演示）
// 即使计算 n=100,000 也不会爆栈（虽然会很慢，因为没有缓存优化）
val fib = DeepRecursiveFunction<Int, BigInteger> { n ->
    if (n <= 1) BigInteger.valueOf(n.toLong()) else {
        callRecursive(n - 1) + callRecursive(n - 2)
    }
}

注意事项

1. 性能开销：由于涉及对象分配和状态机切换，DeepRecursiveFunction 比原生的栈递归要慢一些。仅在确实存在爆栈风险时使用它。对于已知深度较浅的操作（如常见的 UI 视图树遍历），普通递归更好。
2. 调试：由于不使用调用栈，当抛出异常时，传统的 StackTrace 可能不会显示完整的递归路径，这会给调试带来一定困难。