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.
