DeepRecursiveFunction
Defines deep recursive function that keeps its stack on the heap, which allows very deep recursive computations that do not use the actual call stack. To initiate a call to this deep recursive function use its invoke function. As a rule of thumb, it should be used if recursion goes deeper than a thousand calls.
The DeepRecursiveFunction takes one parameter of type T and returns a result of type R.
The block of code defines the body of a recursive function. In this block
callRecursive function can be used to make a recursive call
to the declared function. Other instances of DeepRecursiveFunction can be called
in this scope with callRecursive
extension, too.
For example, take a look at the following recursive tree class and a deeply recursive instance of this tree with 100K nodes:
class Tree(val left: Tree? = null, val right: Tree? = null)
val deepTree = generateSequence(Tree()) { Tree(it) }.take(100_000).last()
A regular recursive function can be defined to compute a depth of a tree:
fun depth(t: Tree?): Int =
if (t == null) 0 else max(depth(t.left), depth(t.right)) + 1
println(depth(deepTree)) // StackOverflowError
If this depth
function is called for a deepTree
it produces StackOverflowError
because of deep recursion.
However, the depth
function can be rewritten using DeepRecursiveFunction
in the following way, and then
it successfully computes depth(deepTree)
expression:
val depth = DeepRecursiveFunction<Tree?, Int> { t ->
if (t == null) 0 else max(callRecursive(t.left), callRecursive(t.right)) + 1
}
println(depth(deepTree)) // Ok
Deep recursive functions can also mutually call each other using a heap for the stack via callRecursive extension. For example, the following pair of mutually recursive functions computes the number of tree nodes at even depth in the tree.
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)
}
}
Parameters
Constructors
<init>
Defines deep recursive function that keeps its stack on the heap, which allows very deep recursive computations that do not use the actual call stack. To initiate a call to this deep recursive function use its invoke function. As a rule of thumb, it should be used if recursion goes deeper than a thousand calls.
DeepRecursiveFunction(
block: suspend DeepRecursiveScope<T, R>.(T) -> R)
Extension Functions
invoke
Initiates a call to this deep recursive function, forming a root of the call tree.
operator fun <T, R> DeepRecursiveFunction<T, R>.invoke(
value: T
): R