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