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.