<init>

Требования к платформе и версии: JVM (1.0), JS (1.0), Native (1.0)

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

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

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

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

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)
    }
}

Параметры

T — тип параметра функции.

R — тип результата функции.

block — тело функции.