DeepRecursiveFunction

Начиная с Kotlin: 1.7

class DeepRecursiveFunction<T, R>(block: suspend DeepRecursiveScope<T, R>.(T) -> R)

Определяет глубоко рекурсивную функцию, которая хранит свой стек в куче, что позволяет выполнять очень глубокие рекурсивные вычисления, не используя фактический стек вызовов. Чтобы инициировать вызов этой глубоко рекурсивной функции, используйте её функцию invoke. Как правило, её следует использовать, если глубина рекурсии превышает тысячу вызовов.

DeepRecursiveFunction принимает один параметр типа T и возвращает результат типа R. Блок кода block задаёт тело рекурсивной функции. В этом блоке можно использовать функцию callRecursive для рекурсивного вызова объявленной функции. В этой области видимости также можно вызывать другие экземпляры DeepRecursiveFunction с помощью расширения callRecursive.

Например, рассмотрим следующий рекурсивный класс дерева и его экземпляр с глубокой рекурсией, содержащий 100 тыс. узлов:

class Tree(val left: Tree? = null, val right: Tree? = null)
val deepTree = generateSequence(Tree()) { Tree(it) }.take(100_000).last()

Обычную рекурсивную функцию для вычисления глубины дерева можно определить так:

fun depth(t: Tree?): Int =
    if (t == null) 0 else max(depth(t.left), depth(t.right)) + 1
println(depth(deepTree)) // StackOverflowError

Если вызвать эту функцию depth для deepTree, возникнет StackOverflowError из-за глубокой рекурсии. Однако функцию depth можно переписать с помощью DeepRecursiveFunction следующим образом, после чего она успешно вычислит выражение depth(deepTree):

val depth = DeepRecursiveFunction<Tree?, Int> { t ->
    if (t == null) 0 else max(callRecursive(t.left), callRecursive(t.right)) + 1
}
println(depth(deepTree)) // Ok

Глубоко рекурсивные функции также могут вызывать друг друга, используя кучу для хранения стека, с помощью расширения callRecursive. Например, следующая пара взаимно рекурсивных функций вычисляет количество узлов дерева, находящихся на чётной глубине.

val mutualRecursion = object {
    val even: DeepRecursiveFunction<Tree?, Int> = DeepRecursiveFunction { t ->
        if (t == null) 0 else odd.callRecursive(t.left) + odd.callRecursive(t.right) + 1
    }
    val odd: DeepRecursiveFunction<Tree?, Int> = DeepRecursiveFunction { t ->
        if (t == null) 0 else even.callRecursive(t.left) + even.callRecursive(t.right)
    }
}

Параметры

Параметры типа