前言

DeepRecursiveFunction 是 Kotlin 在 1.4.0 版本上尝试解决深度递归导致 StackOverflowError 问题的试行方案。在最新发布的 1.7.0 版本上正式 Stable。面对由于递归导致的栈溢出问题，一般我们采用两种解决办法：

• 😔 增加栈大小
• 😄 改写代码，采用非递归方式实现

Kotlin 通过定义 DeepRecursiveFunction 深度递归类型来实现非递归方式的改写。

官方建议：递归深度操作 1000 考虑使用 DeepRecursiveFunction。(Consider using deep recursive functions in your code where your recursion depth exceeds 1000 calls.)

语法

定义

public class DeepRecursiveFunction<T, R>(
    internal val block: suspend DeepRecursiveScope<T, R>.(T) -> R
)
1
2
3

• T 为传入参数类型；
• R 为输出结果类型；
• block 函数体。

调用

public abstract suspend fun callRecursive(value: T): R
1

用于“递归”调用DeepRecursiveFunction

public operator fun DeepRecursiveFunction<*, *>.invoke(value: Any?): Nothing 
1

操作符重载，以便 DeepRecursiveFunction 可以通过()操作符调用，当然也可以选择直接调用invoke函数。

看官方给出的示例对比，可能更直观一点。

示例

实现二叉树的深度计算：原始递归 🆚 DeepRecursiveFunction。

💢原始递归

fun depth(t: Tree?): Int =
    if (t == null) 0 else maxOf(
        depth(t.left), // recursive call one
        depth(t.right) // recursive call two
    ) + 1
1
2
3
4
5

🌞DeepRecursiveFunction

val calculateDepth = DeepRecursiveFunction<Tree?, Int> { t ->
    if (t == null) 0 else maxOf(
        callRecursive(t.left),
        callRecursive(t.right)
    ) + 1
}
1
2
3
4
5
6

对比上面两种代码可以看出，开发者可以很容易从原始递归方式改写成 DeepRecursiveFunction 方式。这就是 Kotlin 希望达到的低开发成本效果。当开发者因采用原始递归方式时递归层级过深出现 StackOverflowError问题时, 简易调整为 DeepRecursiveFunction ，可以在避免大量改写代码的前提下帮助开发者快速解决栈溢出问题。

Run

fun main() {
    // Generate a tree with a depth of 100_000
    val deepTree = generateSequence(Tree(null, null)) { prev ->
        Tree(prev, null)
    }.take(4).last()

    println(calculateDepth(deepTree)) // 100000 
    println(depth(deepTree)) // 100000
}
1
2
3
4
5
6
7
8
9

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LPAOp9KH-1659446563474)(http://qiniu.fultter.club/image-20220731130252997.png)]

源码

关于 DeepRecursiveFunction 的源码全部集中于 DeepRecursive.kt文件中，主要包含三个类：

• DeepRecursiveFunction
• DeepRecursiveScope
• DeepRecursiveScopeImpl

具体的实现集中在 DeepRecursiveScopeImpl 类中，通过协程机制实现递归逻辑。

suspend 模拟向下压栈 ⬇️，resume 模拟向上出栈 ⬆️，实现类似递归调用的效果🪆。

结语

每一颗语法糖背后，总有几个 Kotlin 的工程师在为我们负重前行。🥸