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]`

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([3])`

`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 `[3]` 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.