DeepRecursiveFunction

class DeepRecursiveFunction<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 - тело функции.