Understanding recursion in Elixir

Question

Forgive me if this is basic but I'm new to Elixir and trying to understand the language. Say I have this code

defmodule Test do
  def mult([]), do: 1
  def mult([head | tail]) do
    IO.puts "head is: #{head}"
    IO.inspect tail
    head*mult(tail)
  end
end

when I run with this: Test.mult([1,5,10])

I get the following output

head is: 1
[5, 10]
head is: 5
'\n'
head is: 10
[]
50

But I'm struggling to understand what's going on because if I separately try to do this:

[h | t] = [1,5,10]
h * t

obviously I get an error, can someone explain what I'm missing?

Try to replace `IO.inspect tail` with `IO.inspect tail, charlists: false` and check if any better? — qhwa, Feb 01 '22 at 13:31

Adam Millerchip · Answer 1 · 2022-02-03T02:24:02.570

2

Your function breaks down as:

mult([1 | [5, 10]])
1 * mult([5 | [10]])
1 * 5 * mult([10 | []])
1 * 5 * 10 * mult([])
1 * 5 * 10 * 1
50

The '\n' is actually [10] and is due to this: Elixir lists interpreted as char lists.

IO.inspect('\n', charlists: :as_lists)
[10]

edited Feb 03 '22 at 02:24

answered Feb 03 '22 at 01:20

Adam Millerchip

20,844
5
51
74

thanks for that explanation. it does make sense. One remaining Q I have, where does elixir store the value of each iteration? I think that's the thing that's blocking my full understanding of it – Red Baron Feb 03 '22 at 11:44
That is a very complex question. The short answer is that the virtual machine remembers the context when you call a function, and restores that context when the function returns. Check out https://blog.stenmans.org/theBeamBook/#_working_memory_a_stack_machine_it_is_not – Adam Millerchip Feb 03 '22 at 12:50

score 1 · Accepted Answer · edited Feb 01 '22 at 15:29

Consider the arguments being passed to mult on each invocation.

When you do Test.mult([1,5,10]) first it checks the first function clause; that is can [1,5,10] be made to match []. Elixir will try to make the two expressions match if it can. In this case it cannot so then it tries the next function clause; can [1,5,10] be made to match [head|tail]? Yes it can so it assigns the first element (1) to head and the remaining elements [5,10] to tail. Then it recursively calls the function again but this time with the list [5,10]

Again it tries to match [5,10] to []; again this cannot be made to match so it drops down to [head|tail]. This time head is 5 and tail is 10. So again the function is called recursively with [10]

Again, can [10] be made to match []? No. So again it hits [head|tail] and assigns head = 10 and tail = [] (remember there's always an implied empty list at the end of every list).

Last go round; now [] definitely matches [] so it returns 1. Then the prior head * mult(tail) is evaluated (1 * 10) and that result is returned to the prior call on the stack. Evaluated again head (5) * mult(tail) (10) = 50. Final unwind of the stack head (1) * mult(tail) (50) = 50. Hence the overall value of the function is 50.

Remember that Elixir cannot totally evaluate any function call until it evaluates all subsequent function calls. So it hangs on to the intermediate values in order to compute the final value of the function.

Now consider your second code fragment in terms of pattern matching. [h|t] = [1,5,10] will assign h = 1 and t = [5,10]. h*t means 1 * [5,10]. Since those are fundamentally different types there's no inbuilt definition for multiplication in this case.

very useful answer, thanks. Your penultimate paragraph really helped me. so Elixir is going to take the final value of the recursive function and * it to the value of the exit function (in my case that is 1). so it basically stores the value of the recursive function and then computes it with the exit function. great, really helpful that! — Red Baron, Feb 03 '22 at 11:49

Understanding recursion in Elixir

2 Answers2