ГлубокоРекурсивнаяФункция

class DeepRecursiveFunction<T, R>

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

Функция ГлубокоРекурсивнаяФункция принимает один параметр типа T и возвращает результат типа R. Блок кода определяет тело рекурсивной функции. В этом блоке может использоваться функция callRecursive для рекурсивного вызова объявленной функции. Другие экземпляры ГлубокоРекурсивнаяФункция могут вызываться в этом контексте с помощью 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 — тело функции.