Interesting Kotlin 0x0E: DeepRecursiveFunction

前言

DeepRecursiveFunction 是 Kotlin 在 1.4.0 The version attempts to resolve deep recursion StackOverflowError A trial solution to the problem.在最新发布的 1.7.0 official version Stable.Facing the stack overflow problem due to recursion,Generally we use two solutions：

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

Kotlin 通过定义 DeepRecursiveFunction Deep recursive types to implement non-recursive rewriting.

官方建议：Recursive depth operation 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 Type of the incoming parameter;
• R is the output result type;
• block 函数体.

调用

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

用于“递归”调用DeepRecursiveFunction

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

操作符重载,以便 DeepRecursiveFunction 可以通过()操作符调用,Of course, you can also choose to call directlyinvoke函数.

Look at the official example comparison,可能更直观一点.

示例

Implement the depth calculation of the binary tree：原始递归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
}

It can be seen by comparing the above two codes,Developers can easily rewrite from the original recursive way DeepRecursiveFunction 方式.这就是 Kotlin The desired effect of low development costs.The recursion level is too deep when developers use primitive recursion StackOverflowError问题时, easy to adjust to DeepRecursiveFunction ,It can help developers quickly solve stack overflow problems on the premise of avoiding a lot of code rewriting.

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
}

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

源码

关于 DeepRecursiveFunction The source code is all concentrated in DeepRecursive.kt文件中,There are mainly three categories：

• DeepRecursiveFunction
• DeepRecursiveScope
• DeepRecursiveScopeImpl

The specific implementation focuses on DeepRecursiveScopeImpl 类中,The recursive logic is implemented through the coroutine mechanism.

suspend Simulates pushing down the stack ️,resume Simulates popping up the stack ️,To achieve an effect similar to recursive calls🪆.

结语

Behind every piece of syntactic sugar,总有几个 Kotlin of engineers are carrying the weight for us.🥸