# Deep recursion with coroutines

DevFeed: [Deep recursion with coroutines](<https://devfeed.tech/articles/deep-recursion-with-coroutines-26021.md>)

Original publisher: [Read original article](<https://elizarov.medium.com/deep-recursion-with-coroutines-7c53e15993e3?source=rss-4762e889f8fc------2>)

Author: Roman Elizarov

Published: 2020-04-25T20:33:55Z

Content type: tutorial

Language: en

Sources: [Stories by Roman Elizarov on Medium](<https://devfeed.tech/sources/stories-by-roman-elizarov-on-medium.md>)

Topics: [Coroutines](<https://devfeed.tech/topics/coroutines.md>), [Kotlin](<https://devfeed.tech/topics/kotlin.md>), [Data structures](<https://devfeed.tech/topics/data-structures.md>), [Programming](<https://devfeed.tech/topics/programming.md>)

Tags: [coroutine](<https://devfeed.tech/tags/coroutine.md>), [coroutines](<https://devfeed.tech/tags/coroutines.md>), [data-structures](<https://devfeed.tech/tags/data-structures.md>), [exception](<https://devfeed.tech/tags/exception.md>), [jvm](<https://devfeed.tech/tags/jvm.md>), [kotlin](<https://devfeed.tech/tags/kotlin.md>), [kotlin-coroutines](<https://devfeed.tech/tags/kotlin-coroutines.md>), [recursion](<https://devfeed.tech/tags/recursion.md>)

## AI overview

This tutorial explains how Kotlin coroutines can be used to handle deeply recursive functions. Using a 100,000-node binary tree as an example, it shows that ordinary recursion can exhaust the thread call stack and lead to a StackOverflowError, then introduces rewriting the algorithm to use heap memory instead.

## Source excerpt

Photo by Riccardo Pelati on Unsplash Kotlin Coroutines are typically used for asynchronous programming. However, the underlying design of coroutines and their implementation in Kotlin compiler are quite universal, solving problems beyond asynchronous programming. Let's take a look at one such problem that can be elegantly solved with coroutines-- writing deeply recursive functions. Setup Consider a tree data structure. For this example, let's use this simple binary tree where each Tree node has a reference to its left and right children: class Tree(val left: Tree?, val right: Tree?) The depth of the tree is defined as the length of the longest path from its root to its child nodes. It can be computed by the following recursive function: fun depth(t: Tree?): Int = if (t == null) 0 else maxOf( depth(t.left), // recursive call one depth(t.right) // recursive call two ) + 1 The logic here is straightforward. The depth is simply the maximum of the depth of the left and right children plus one, with the special case of zero when the tree is empty. Recursion is a great tool for working with tree-like data structures, but there is a catch. Let's generate a deep tree containing 100K nodes. Start with a leaf node Tree(null, null) as a seed and repeatedly generate parent nodes that link to the previous node as their left children: val n = 100_000 val deepTree = generateSequence(Tree(null, null)) { prev -> Tree(prev, null) }.take(n).last() This is not a particularly big data structure. It occupies less than 2MiB of memory, which is not much at all for a modern machine with gigabytes of available memory. Now, let's try to use our depth function on it: https://medium.com/media/f919e36404c4bf79aef919395ab51918/href If you run it in Kotlin Playground you'll get "Your program produces too much output!" message. If you run the same code on your local machine you'll see what kind of output that is: Exception in thread "main" java.lang.StackOverflowError at FileKt.depth(File.kt:5) ... /