当前位置：网站首页>有趣的 Kotlin 0x0E：DeepRecursiveFunction

有趣的 Kotlin 0x0E：DeepRecursiveFunction

2022-08-04 04:37:00 【AndroidKt】

前言

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
)

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
}