How does recursion work in Elixir

5
votes

Simple function in Elixir, returning a list of numbers from to:

defmodule MyList do

  def span(_), do: raise "Should be 2 args"
  def span(from, to) when from > to,  do: [ to | span(to + 1, from) ]
  def span(from, to) when from < to,  do: [ from | span(from + 1, to) ]
  def span(from, to) when from == to, do: [ from ]
end

I have no slightest clue, why this works and return a list of numbers.

MyList.span(1,5)
#=> [1,2,3,4,5]

I just can't get my head around this:

[ from | span(from + 1, to) ]

Ok, first loop, I assume, would return the following:

[ 1 | span(2, 5) ]

What is next? [ 1, 2 | span(3, 5) ] ? Why?

How does it know, when to stop? Why is it even working?

Please, do not chase the points - don't bother answering, if you are not going to make an effort to make things clear(er) for functional programmer noob (OO programmer).

As a bonus to the answer you could provide me with a tips on how to start think recursively? Is there any panacea?

How does it keep track of the head? How does the function creates new list on each iteration keeping the values produced in the previous?

Thanks!

1
recursionelixir
As @whatyouhide said, it's more like [ 1 | [ 2 | [ 3 | [ 4 | [ 5 ]]]]], which evaluates to [1, 2, 3, 4, 5] – asymmetric

1 Answers

13
votes

Ok, let's give this a shot.

Erlang evaluates function calls with a call-by-value strategy. From the linked wikipedia:

[call-by-value is a] family of evaluation strategies in which a function's argument is evaluated before being passed to the function.

What this means is that when Elixir (or rather Erlang) sees a function call with some arguments, it evaluates the arguments (which can obviously be expressions as well) before calling the function.

For example, let's take this function:

def add(a, b), do: a + b

If I call it with two expressions as arguments, those expressions will be evaluated before the the results are added up:

add(10 * 2, 5 - 3)
# becomes:
add(20, 2)
# kind of becomes:
20 + 2
# which results in:
22

Now that we get call-by-value, let's think of the | construct in list as a function for a moment. Think of it like if it would be used like this:

|(1, [])         #=> [1]
|(29, [1, 2, 3]) #=> [29, 1, 2, 3]

As all functions, | evaluates its arguments before doing its work (which is creating a new list with the first argument as the first element and the second argument as the rest of the list).

When you call span(1, 5), it kind of expands (let's say it expands) to:

|(1, span(2, 5))

Now, since all arguments to | have to be evaluated before being able to actually prepend 1 to span(2, 5), we have to evaluate span(2, 5). This goes on for a while:

|(1, |(2, span(3, 5)))
|(1, |(2, |(3, span(4, 5))))
|(1, |(2, |(3, |(4, span(5, 5)))))
|(1, |(2, |(3, |(4, [5]))))))
# now, it starts to "unwind" back:
|(1, |(2, |(3, [4, 5])))
|(1, |(2, [3, 4, 5]))
|(1, [2, 3, 4, 5])
[1, 2, 3, 4, 5]

(sorry if I'm using this |() syntax, remember I'm just using | as a function instead of an operator).

Nothing keeps track of the head and no function "keeps the values produced in the previous [iteration]". The first call (span(1, 5)) just expands to [1|span(2, 5)]. Now, in order for the span(1, 5) call to return, it needs to evaluate [1|span(2, 5)]: there you have it, recursion! It will need to evaluate span(2, 5) first and so on.

Technically, the values are kept somewhere, and it's on the stack: each function call is placed on the stack and popped off only when it's able to return. So the stack will look something like the series of calls I showed above:

# First call is pushed on the stack
span(1, 5)
# Second call is pushed on top of that
span(1, 5), span(2, 5)
# ...
span(1, 5), span(2, 5), ..., span(5, 5)
# hey! span(5, 5) is not recursive, we can return [5]. Let's pop span(5, 5) from the stack then
span(1, 5), ..., span(4, 5)
# Now span(4, 5) can return because we know the value of span(5, 5) (remember, span(4, 5) is expanded to [4|span(5, 5)]

This goes on until it goes back to span(1, 5) (which is now span(1, [2, 3, 4, 5])) and finally to [1, 2, 3, 4, 5].

Ok I wrote a lot and I'm not sure I made anything clearer to you :). Please, ask anything that's not clear. There are surely a lot of resources to learn recursion out there; just to name the first bunch I found: