Tail Recursive Functions

Summary

The web content introduces tail recursive functions in Kotlin, emphasizing the tailrec keyword for stack overflow prevention and mentioning advanced techniques like trampolining and the DeepRecursiveFunction for handling deep recursion.

Abstract

The article briefly discusses tail recursive functions in the context of Kotlin programming, highlighting the importance of the tailrec keyword to enable tail-call optimization and avoid stack overflow errors. It suggests that while understanding tail recursion is not mandatory for Kotlin developers, it is a useful concept to be aware of, especially when dealing with functional programming and recursive functions. The content also touches on the complexity of manually converting recursive functions into tail-recursive form and points to libraries and Kotlin's standard library for solutions to handle deep recursion, such as the DeepRecursiveFunction. The article is part of the "Kotlin Primer" series and encourages further reading on the subject matter through provided resources and external links.

Opinions

The author believes that knowledge of tail recursion is beneficial but not a prerequisite for Kotlin developers.
The article suggests that writing recursive functions in tail-recursive form can be tedious without the help of libraries or language features.
It is implied that the use cases for advanced recursion techniques, such as DeepRecursiveFunction, are relatively narrow in typical enterprise applications.
The author expresses gratitude to Etnetera a.s. for supporting the creation of the "Kotlin Primer" series.
The article encourages self-directed learning by recommending that readers Google terms and concepts related to tail recursion and trampolining.

A brief note on tail recursive functions, trampolining and DeepRecursiveFunction.

— — — — — — — — — — — — — — —

THE CURRENT VERSION OF THIS ARTICLE IS PUBLISHED HERE.

— — — — — — — — — — — — — — —

This article is part of the Kotlin Primer, an opinionated guide to the Kotlin language, which is indented to help facilitate Kotlin adoption inside Java-centric organizations. It was originally written as an organizational learning resource for Etnetera a.s. and I would like to express my sincere gratitude for their support.

It is recommended to read the Introduction before moving on. Check out the Table of Contents for all articles.

We’re just briefly going to mention this, so you’re aware that it exists.

As you get more and more versed in functional programming, you may find yourself writing (or wanting to write) recursive functions, i.e. functions that call themselves. A problem often associated with recursive functions is stack overflow, i.e. the function calling itself so many times that the stack runs out of space.

To help with that, Kotlin offers the tailrec keyword, which allows the compiler to take advantage of a form of recursion called tail recursion. When this form of recursion is used, the compiler can use tail-call optimization which prevents stack overflows from happening (but you can still get infinite loops).

You are encouraged to Google those terms and learn about them, they’re a useful tool to have in your belt. However, being proficient in tail recursion is not a prerequisite for being a Kotlin developer, so we won’t go into them here. Just keeps this vaguely in mind, and come back to it if you ever find yourself writing a lot of recursive functions.

While it is always possible to write recursive functions in tail-call form using certain techniques involving continuations, it’s often tedious to do so. Lucky for us, there are libraries that implement those techniques, and there’s even a standard library component implemented exactly for this purpose. However, we won’t go into detail, because it’s an advanced topic with a fairly narrow range of use-cases in the average enterprise application.

You can find out more about the keyword in the documentation.