Understanding recursion in Elixir

user_10795348 0
Viewed 121

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?

elixir recursion
2 Answers

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

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.

Onorio_Catenacci_28200
Related