Chapter 4. Recursion, corecursion, and memoization

The previous chapter introduced powerful methods and functions, but some shouldn’t be used in production because they can overflow the stack and crash the application (or at least the thread in which they’re called). These “dangerous” methods and functions are mainly explicitly recursive, but not always. You’ve seen that composing functions can also overflow the stack, and this can occur even with nonrecursive functions, although this isn’t common.

In this chapter, you’ll learn how to turn stack-based functions into heap-based functions. This is necessary because the stack is a limited memory area. For recursive functions to be safe, you have to implement them in such a way that they use the heap (the main memory area) instead of the limited stack space. To understand the problem completely, you must first understand the difference between recursion and corecursion.

4.1. Understanding corecursion and recursion

Corecursion is composing computing 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 starting with the last step. In recursion, you have to delay evaluation until you encounter a base condition (corresponding to the first step of corecursion).

4.2. Working with recursive functions

4.3. Composing a huge number of functions

4.4. Using memoization

4.5. Summary