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

}

}

#### Since Kotlin

1.7#### Parameters

__T__

the function parameter type.

__R__

the function result type.

__block__

the function body.

Since Kotlin1.7