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. |