The importance of recursion

First, let's make sure we understand what recursion is. Let's think about how we pull apart Russian Dolls.

Recursion works like the process of finding the smallest doll. We repeat the same process, i.e., pulling apart the doll until we find a doll that is solid. Though our problems get smaller, the problem solving process is the same as the previous because the structure of the nesting dolls is the same. Each doll is a smaller than the previous one. Eventually, we get to a doll that's too small to have a doll inside it and we're done. That's the fundamental idea behind recursion.

We also need to understand how to to write a tail recursive function because that's the kind of recursion that's a candidate for TCO. When our recursive function that calls itself as its last action, then we can reuse the stack frame of that function. The tSum function in the previous section is an example of tail recursion.

Understanding recursion marks a transition for us from a programmer to a computer scientist. Recursion requires some mathematical sophistication to understand, but once  we master it we'll find that it opens up a plethora of ways to solve important problems.

A soccer coach would not have his player practice kicking balls down hill to a target; that scenario will never occur in a game. Similarly, we will not spend a lot of time pursuing recursive implementations in Go.

A tail recursive function is the functional form of a loop, and with TCO it executes just as efficiently as a loop. Without recursion, we must implement most loops using imperative programming techniques. Thus, having TCO in Go would actually be more beneficial to FP than Generics. We'll learn more about Generics in Chapters 9, Functors, Monoids, and Generics and Chapter 10, Monads, Type Classes, and Generics. See the How to Propose Changes To Go  section in the Appendix or jump directly to the discussion regarding adding TCO to Go at https://github.com/golang/go/issues/22624.