DeepRecursiveFunction

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