Understanding Recursion with Elixir

Sophie DeBenedetto on January 21, 2019

This post was originally published on the Elixir School blog. Elixir School is an open source Elixir curriculum and we're looking for contributor... [Read Full]
markdown guide
 

Please fix RecursionPractice example by introducing the header clause:

defmodule RecursionPractice do
  def hello_world(count \\ 0) # ⇐ THIS

  def hello_world(count) when count >= 10, do: nil
  def hello_world(count) do
    IO.puts("Hello, World!")
    new_count = count + 1
    hello_world(new_count)
  end
end

Without the header, it produces the warning during compilation stage and would not probably compile at all as of Elixir 2.0.


Also, instead of the explicit comparison one might use direct matches inside function clauses

- def delete_all([head | tail], el, new_list) when head === el do
+ def delete_all([el | tail], el, new_list) do # ⇐ NOTE 2 el
 

Thanks for pointing these out! I've updated the post to use a header clause for that default argument and included a link to some more info for anyone who wants a deeper understanding of why that's needed.

Your second suggestion looks good too, I'll incorporate a note to that effect in the post later on today.

 

What's the header do / why is it needed?

And I was totally wondering if it could do that with the variable!

 

It declares the function of the desired arity for cases like def foo(p1, p2 \\ nil, p3).

Not sure I understand. Are you saying that all versions of the function have to have the same arity, so it needs a default value in order to have arity of 1 instead of zero?

My Elixir (1.7.4) didn't have any issue with it. Admittedly, you said it might be an Elixir 2 thing, but still, I'd expect arity to vary across signatures.

defmodule A do
  def b,      do: IO.puts "I am b"
  def b(arg), do: IO.puts "I am b(#{arg})"
end

A.b
A.b 123

Or maybe when you say "declare", it's like a C style declaration, where you're telling the compiler the signature so it can type map a call to a function signature before seeing the definition?

No, no, clauses with different arities are fine. Multiple clauses of the same arity with defaults are not. If it leads to ambiguity, Elixir compiler raises.

iex|1  defmodule M do                      
...|1    def foo(_arg1 \\ nil, arg2), do: arg2
...|1    def foo(arg1, _arg2 \\ nil), do: arg1
...|1  end

** (CompileError) iex:1: def foo/2 defines defaults multiple times. Elixir allows defaults to be declared once per definition. Instead of:

    def foo(:first_clause, b \\ :default) do ... end
    def foo(:second_clause, b \\ :default) do ... end

one should write:

    def foo(a, b \\ :default)
    def foo(:first_clause, b) do ... end
    def foo(:second_clause, b) do ... end

When Elixir is able to handle multiple clauses without ambiguity, it issues a warning.

iex|2  defmodule M do                       
...|2    def foo(arg1, _arg2 \\ nil), do: arg1
...|2    def foo(arg1, arg2), do: arg1 <> arg2
...|2  end

warning: def foo/2 has multiple clauses and also declares default values. In such cases, the default values should be defined in a header. Instead of:

    def foo(:first_clause, b \\ :default) do ... end
    def foo(:second_clause, b) do ... end

one should write:

    def foo(a, b \\ :default)
    def foo(:first_clause, b) do ... end
    def foo(:second_clause, b) do ... end

But still, the head clause should be used to avoid possible human mistakes and make the intent clear.

 

Hi @sophiedebenedetto ,

I propose you a smaller solution:

defmodule MyList do
  def delete_all([head | tail], el) when head === el do
    delete_all(tail, el)
  end

  def delete_all([head | tail], el) do
    [head | delete_all(tail, el)]
  end

  def delete_all([], _) do
    []
  end  
end

I think is better because we get rid of additional parameter new_list and no need to reverse final result.
My first time coding in Elixir. Looks very nice at first glance.
Reminds me of the time when I played with Ruby and Haskell.

Thank you for the post

 

Awesome! I love this solution, definitely more simple. Thanks for sharing!

 

Is Elixir able to do this efficiently? In particular, I'm wondering about the callstack, does it keep the frame on the stack while it figures out the RHS of the list, or is it smart enough to build the list element (presumably called cons, at least that's what they'd call it in lisp), and then fill in the RHS values as they become available?

I seriously didn't know that Elixir had tail call optimization, that is super fkn cool! lol, but now I'm all curious how it works. If you gave these 2 solutions a really long list, I assume the last entry from the blog would be fine, but what about the code in this comment? If it can handle this code without stack overflowing, that would be extremely cool (if it works, then I'm guessing lists would have to have a special case somewhere in the compiler or interpreter).

Of course ErlangVM has TCO. Elixir leverages ErlangVM, so yes, TCO is there for free.

code of conduct - report abuse