Recursion: Let’s Look at Lists
List data structure — and the head and tail components of a
List — are so important to recursion, it helps to visualize what a list and its head and tail components look like. Figure [fig:headTailWorm] shows one way to visualize a
This creative imagery comes from the online version of “Learn You a Haskell for Great Good”, and it does a great job of imprinting the concept of head and tail components of a list into your brain. As shown, the “head” component is simply the first element in the list, and the “tail” is the rest of the list.
A slightly more technical way to visualize the head and tail of a list is shown in Figure [fig:visualizeListMoreTech].
An even more accurate way to show this is with a
Nil value at the end of the
List, as shown in Figure [fig:visualizeListNilElement], because that’s what it really looks like:
To be clear, the
List that I’m talking about is a linked list — scala.collection.immutable.List, which is the default list you get if you type
List in your IDE or the REPL. This
List is a series of cells, where each cell contains two things: (a) a value, and (b) a pointer to the next cell. This is shown in Figure [fig:linkedListDepiction].
As shown, the last cell in a linked list contains the
Nil value. The
Nil in the last cell is very important: it’s how your recursive Scala code will know when it has reached the end of a
When drawing a list like this, Figure [fig:headElemOfAList] clearly shows the head element of a list, and Figure [fig:tailElemsOfAList] shows the tail elements.
Just like Haskell — and Lisp before it — the default Scala
List works with these head and tail components, and I’ll use them extensively in the examples that follow.
For historical reasons these cells are known as “cons cells.” That name comes from Lisp, and if you like history, you can read more about it on Wikipedia.
As a first note about
List with no elements in it is an empty list. An empty
List contains only one cell, and that cell contains a
Nil element, as shown in Figure [fig:theNilList].
You can create an empty
List in Scala in two ways:
scala> val empty = List() empty: List[Nothing] = List() scala> val empty = Nil empty: scala.collection.immutable.Nil.type = List()
Because I haven’t given those lists a data type (like
Int), the results look a little different, but if I add a type to those expressions, you’ll see that the result is exactly the same:
scala> val empty1: List[Int] = List() empty: List[Int] = List() scala> val empty2: List[Int] = Nil empty: List[Int] = List() scala> empty1 == empty2 res0: Boolean = true
List() == Nil
There are several ways to create non-empty
Lists in Scala, but for the most part I’ll use two approaches. First, here’s a technique you’re probably already familiar with:
val list = List(1,2,3)
Second, this is an approach you may not have seen yet:
val list = 1 :: 2 :: 3 :: Nil
These two techniques result in the exact same
List[Int], which you can see in the REPL:
scala> val list1 = List(1,2,3) list: List[Int] = List(1, 2, 3) scala> val list2 = 1 :: 2 :: 3 :: Nil list: List[Int] = List(1, 2, 3) scala> list1 == list2 res1: Boolean = true
The second approach is known as using “cons cells.” As you can see, it’s a very literal approach to creating a
List, where you specify each element in the
List, including the
Nil element, which must be in the last position. If you forget the
Nil element at the end, the Scala compiler will bark at you:
scala> val list = 1 :: 2 :: 3 <console>:10: error: value :: is not a member of Int val list = 1 :: 2 :: 3 ^
I show this because it’s important — very important — to know that the last element in a
List must be the
Nil element. (I like to say that the
Nil element is to a
List as a caboose is to a train.) We’re going to take advantage of this knowledge as we write our first recursive function.