Something is said to be recursive if defined in terms of itself.
In TypeScript, recursion can be utilised for defining recursive types and recursive functions. In the code examples to follow, we’ll show both. Let’s create a type representing a general purpose tree structure first:
You can see that every node in our tree includes a value of type A, and can have an unbounded number of subtrees.
If we wanted to count the nodes our tree consists of using recursion, we could do it like this:
This code is very concise and readable — basically we’ve defined that we get tree node count by adding 1 to the sum of the node count of all subtrees (we could even verify the correctness of our function using mathematical induction, but it’s beyond the scope of this post).
Everything feels fine and dandy with this piece of code in production, until we come across a deep enough tree and try to count its nodes.
Here comes the distant cousin of an error so famous that it became the name of our precious lord and saviour - Stack Overflow. Fun fact: do not try to search for “stack overflow” on Stack Overflow. It’s not that the internet would go boom, it just simply won't find any relevant answers 😃.
To avoid blowing the stack, we need to make our function tail recursive — meaning a recursive call is the last thing executed by the function. Unfortunately, this condition is not met in our countNodes function. The last thing we do is actually adding 1 to the sum of the node count of all subtrees. We can, however, easily transform function as follows:
We introduced a local <inline-code>iterate<inline-code> function that does the computation. We carry the intermediate result here as the last argument, so the call to <inline-code>iterate<inline-code> can be the last thing executed. That's why there is actually no need for function context, precisely because we just return the value from the function.
Nothing is lost though — we can optimise the code by ourselves and the change is rather trivial:
Instead of recursively calling <inline-code>iterate<inline-code> directly, we return the function that calls it. This way we prevent stacking contexts, and simply call the result in a loop until there is a final result.
This simple technique is often called trampolining, and no, I wont search for any funny picture with a trampoline in it 😉.
To prevent us from duplicating the code again and again, we can generalise the trampolining and type safety at the same time.
So what did we do here? We’ve prepared a type representing the return value from our recursive function. It is a union type describing either final result (<inline-code>Value<inline-code>), or a yet-to-called function to get the final result (<inline-code>Recurse<inline-code>).
If you are wondering what the purpose of _tag property is, check TypeScript: Documentation - Narrowing for more details. Basically it allows us to do exhaustive checking in a switch case for each possible variant of the Trampoline type.
We also implemented the <inline-code>trampolined<inline-code> combinator. If passed on the tail recursive function which returns the <inline-code>Trampoline<inline-code> type, it provides us with a result function that does the trampolining trick:
If you are unsure about that type-fu in the trampolined function signature, it’s used to correctly preserve types of function f arguments. Check the following github issue if you are interested in learning more.
With a few finishing touches to the <inline-code>iterate<inline-code> function, we can finally apply a trampolined combinator and start to celebrate the outcome!
Stay safe and recursive!
Když Martin svým iOS kódem zrovna nezachraňuje životy, organizuje pro ostatní Cookielabbers výlety po Tatrách a vzdělává je v tajích slovenštiny.
„Pro mobilní vývoj byla největší výzva vyzkoušet si Jetpack Compose, se kterým jsme dosud nepracovali. Nakonec jsme dokázali aplikaci vytvořit ve velmi krátkém čase a Vito se mohl vrhnout na implementaci Firebase ML knihovny pro rozpoznávání čárových kódů. Pro komunikaci s backendem jsme použili Retrofit, což asi žádného ostříleného Android vývojáře nepřekvapí,“ shrnuje Martin.
Zařízené kanceláře, vybavené zasedačky, skvělá káva i relax zóna. Kdo nám chybí je spolubydlící firma. Někdo s láskou k dobré kávě, vychlazenému pivu a černému humoru.