# Thinking recursion in Elixir

Published October 09, 2018 by Toran Billups

In part 15 of my Elixir journey I wanted to share how I think about recursion at the most basic level.

### Recursion

The `sum` function should enumerate each item in the list and return the total.

```    `defmodule Math do`
`  def sum([]), do: 0`
`  def sum([head | tail]) do`
`    head + sum(tail)`
`  end`
`end`
```

To solve this problem in Elixir I had to think differently. Instead of using a `for loop` like I've done for so many years in imperative languages I had to (re)learn recursion.

Taking a step by step approach I wanted to describe how this `sum` function works in great detail to get a sense of how the program behaves at runtime.

```    `Math.sum([1, 2, 3])`
```

1) head is the integer `1` and tail is the list `[2, 3]`

2) head is the integer `2` and tail is the list ``

3) head is the integer `3` and tail is an empty list `[]`

4) empty list `[]` is a match for the first `sum` clause

We can calculate the `sum` of our list by walking through the previous set of instructions in reverse. It's worth mentioning that each time the `sum` function calls itself, it adds to the stack. And when the `sum` function returns it will pop off the stack (hence the reverse order).

```    `0 # sum([])`
`3 + 0 # sum()`
`2 + 3 # sum([2, 3])`
`1 + 5 # sum([1, 2, 3])`
```

The first call on the stack as we start to unwind executes `sum` with an empty list `[]` and returns the integer `0`. The next call on the stack executes `sum` with the list `` and returns the integer `3` + `0` (prior `sum` result). The next call on the stack executes `sum` with `[2, 3]` and returns the integer `2` + `3` (prior `sum` result). The very last call on the stack invokes `sum` with `[1, 2, 3]` and returns the integer `1` + `5` (prior `sum` result). The final value returned from this `sum` function is `6` (no surprise I hope).

This type of thinking becomes more familiar with time and offers some compelling solutions to a diverse set of problems. One day soon I hope the `for loop` concept becomes so foreign that I reach for recursion straight away.