# 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)`.
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`.