Recursion: A Conversation Between Two Developers

As an homage to one of my favorite Lisp books — an early version of what is now The Little Schemer — this lesson shows a little question and answer interaction that you can imagine happening between two Scala programmers.

Given this sum function:

def sum(list: List[Int]): Int = list match {
    case Nil => 0
    case x :: xs => x + sum(xs)
}

I hope this “conversation” will help drive home some of the points about how recursion works:

Person 1 Person 2
What is this? val x = List(1,2,3,4) An expression that defines a List[Int], which in this case contains the integers 1 through 4. The expression binds that list to the variable x.
And what is this? x.head The first element of the list x, which is 1.
How about this? x.tail That’s the remaining elements in the list x, which is List(2,3,4).
How about this: x.tail.head It is the number 2.
How did you come up with that? x.tail is List(2,3,4), and List(2,3,4).head is the first element of that list, or 2.
How about this: x.tail.tail That’s List(3,4).
Explain, please. x.tail is List(2,3,4), and then List(2,3,4).tail is List(3,4).
Are you ready for more? Yes, please.
Given the definition of our sum function, explain the first step in: sum(List(1,2,3)). The sum function receives List(1,2,3). This does not match the Nil case, but does match the second case, where x is assigned to 1 and xs is List(2,3).
Then what happens? A new instance of sum is called with the parameter List(2,3).
And then? A new instance of sum receives the input parameter List(2,3). This does not match the Nil case, but does match the second case, where x is assigned to 2 and xs is List(3).
Please continue. sum is called with the parameter List(3).
Go on. A new instance of sum receives List(3). This does not match the Nil case, but does match the second case, where x is assigned to 3 and xs is List().
Don't stop now. sum is called with the parameter List().
What happens inside this instance of sum? It receives List(). This is the same as Nil, so it matches the first case.
Cool. Something different. Now what happens? That case returns 0.
Ah, finally a return value! You’re telling me.
Okay, so now what happens? This ends the recursion, and then the recursive calls unwind, as described in the previous lesson.

books i’ve written