4 Recursion, corecursion, and memoization

Recursive functions are a ubiquitous feature in many programming languages, although those are seldom used in Java. That’s because of the poor implementation of this functionality. Fortunately, Kotlin offers a much better implementation, so that you can use recursion widely.

With recursion, many algorithms are defined recursively. Implementing these algorithms in non-recursive languages consists mainly of translating recursive algorithms into non-recursive ones. Using a language capable of handling recursion not only simplifies coding, but also allows writing programs that reflect the intention (the original algorithm). Such programs are generally much easier to read and to understand. And programming is much more about reading programs that writing them, so it’s important to create programs that clearly show what’s done rather than how it’s done.

4.1 Corecursion and recursion

Corecursion is composing computation steps by using the output of one step as the input of the next one, starting with the first step. Recursion is the same operation but starts with the last step. Let’s take as an example a list of characters that you want to join into a string representation.

4.1.1 Implementing corecursion

4.1.2 Implementing recursion

4.1.3 Differentiating recursive and corecursive functions

4.1.4 Choosing recursion or corecursion

4.2 Tail Call Elimination

4.2.1 Using Tail Call Elimination

4.2.2 Switching from loops to corecursion

4.2.3 Using recursive value functions

4.3 Recursive functions and lists

4.3.1 Using doubly recursive functions

4.3.2 Abstracting recursion on lists

4.3.3 Reversing a list

4.3.4 Building corecursive lists

4.3.5 The danger of strictness

4.4 Memoization

4.4.1 Using memoization in loop-based programming

4.4.2 Using memoization in recursive functions

4.4.3 Using implicit memoization

4.4.4 Using automatic memoization

4.4.5 Implementing memoization of multi-argument functions

4.5 Are memoized functions pure?

Summary