有趣的 Kotlin 0x0E:DeepRecursiveFunction

前言

DeepRecursiveFunctionKotlin 在 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
)
  • T 为传入参数类型;
  • R 为输出结果类型;
  • block 函数体。

调用

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

用于“递归”调用DeepRecursiveFunction

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

操作符重载,以便 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

?DeepRecursiveFunction

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

对比上面两种代码可以看出,开发者可以很容易从原始递归方式改写成 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
}

源码

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

  • DeepRecursiveFunction
  • DeepRecursiveScope
  • DeepRecursiveScopeImpl

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

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

结语

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

作者:易冬

%s 个评论

要回复文章请先登录注册