Chapter 4. Logic and Recursion

So far, Elixir seems logical but fairly simple. Pattern matching controls the flow through a program, and requests that match a form return certain responses. While this is enough to get many things done, sometimes you’ll want more powerful options, especially as you start working with larger and more complicated data structures.

Logic Inside of Functions

Pattern matching and guards are powerful tools, but there are times when it’s much easier to do some comparisons inside of a function clause instead of creating new functions. Elixir’s designers agreed and created two constructs for evaluating conditions inside of functions: the case expression and the less frequently used cond and if expressions.

The case construct lets you use pattern matching and guards inside of a function clause. It reads most clearly when a single value (or set of values) needs to be compared with multiple possibilities. The cond construct evaluates only a series of expressions, without pattern matching. The cond construct tends to produce more readable code in situations where the multiple possibilities are specified by combinations of different values. The if construct evaluates only a single expression.

All these constructs return a value your code can capture.

Evaluating Cases

The case construct lets you perform pattern matching inside of your function clause. If you found the multiple function clauses of Example 3-2 hard to read, you might prefer to create a version that looks like Example 4-1, which you can find in ch04/ex1-case.

Example 4-1. Moving pattern matching inside the function with case
defmodule Drop do

  def fall_velocity(planemo, distance) when distance >= 0 do
    case planemo do
     :earth -> :math.sqrt(2 * 9.8 * distance)
     :moon  -> :math.sqrt(2 * 1.6 * distance)
     :mars  -> :math.sqrt(2 * 3.71 * distance)
    end
  end

end

The case construct will compare the atom in planemo to the values listed, going down the list in order. It won’t process beyond the first match it finds. Each matching value is followed by a ->, which you can read as “yields.” The case construct will return the result of different calculations based on which atom is used, and because the case construct returns the last value in the function clause, the function will return that value as well.

Note

You can use the underscore (_) for your pattern match if you want a choice that matches “everything else.” However, you should always put that last—nothing that comes after it will ever be evaluated.

The results should look familiar:

iex(1)> Drop.fall_velocity(:earth, 20)
19.79898987322333
iex(2)> Drop.fall_velocity(:moon, 20)
8.0
iex(3)> Drop.fall_velocity(:mars, -20)
** (FunctionClauseError) no function clause matching in Drop.fall_velocity/2
    (drop) lib/drop.ex:3: Drop.fall_velocity(:mars, -20)

The case construct switches among planemos, while the guard clause on the function definition keeps out negative distances, producing (rightly) the error on line 3. This way the guard needs to appear only once.

You can also use the return value from the case construct to reduce duplicate code and make the logic of your program clearer. In this case, the only difference between the calculations for earth, moon, and mars is a gravitational constant. Example 4-2, which you can find in ch04/ex2-case, shows how to make the case construct return the gravitational constant for use in a single calculation at the end.

Example 4-2. Using the return value of the case construct to clean up the function
defmodule Drop do

  def fall_velocity(planemo, distance) when distance >= 0 do
    gravity = case planemo do
     :earth -> 9.8
     :moon  -> 1.6
     :mars  -> 3.71
    end
    :math.sqrt(2 * gravity * distance)
  end

end

This time, the gravity variable is set to the return value of the case construct. The now more readable formula math:sqrt(2 * gravity * distance) is the last line of the function, and the value it produces will be the return value.

You can also use guards with a case statement, as shown, perhaps less than elegantly, in Example 4-3, which is in ch04/ex3-case. This might make more sense if there were different planemos with different rules about distances.

Example 4-3. Moving guards into the case statement
defmodule Drop do

  def fall_velocity(planemo, distance)  do
    gravity = case planemo do
     :earth when distance >= 0 -> 9.8
     :moon when distance >= 0  -> 1.6
     :mars when distance >= 0  -> 3.71
    end
    :math.sqrt(2 * gravity * distance)
  end

end

This produces similar results, except that the error message at the end changes from a FunctionClauseError to a CaseClauseError:

iex(3)> r(Drop)
warning: redefining module Drop (current version defined in memory)
  lib/drop.ex:1

{:reloaded, Drop, [Drop]}
iex(4)> Drop.fall_velocity(:earth, 20)
19.79898987322333
iex(5)> Drop.fall_velocity(:moon, 20)
8.0
iex(6)> Drop.fall_velocity(:mars, -20)
** (CaseClauseError) no case clause matching: :mars
    (drop) lib/drop.ex:4: Drop.fall_velocity/2

The error is correct, in that the case construct is trying to match :mars, but misleading because the problem isn’t with :mars but rather with the guard that’s checking the distance variable. If Elixir tells you that your case doesn’t match, but a match is obviously right there in front of you, check your guard statements.

Adjusting to Conditions

The cond construct is broadly similar to the case statement, but without the pattern matching. If you would like, this allows you to write a catch-all clause—an expression matching true at the end. This often makes it easier to express logic based on broader comparisons than simple matching.

Suppose, for example, that the precision of the fall_velocity function is too great. Instead of an actual speed, you’d like to describe the relative speed produced by dropping from a tower of a given height. You can add a cond construct that does that to the earlier code from Example 4-2, as shown in Example 4-4 (in ch04/ex4-cond).

Example 4-4. Adding a cond construct to convert numbers into atoms
defmodule Drop do

  def fall_velocity(planemo, distance) when distance >= 0 do
    gravity = case planemo do
     :earth -> 9.8
     :moon  -> 1.6
     :mars  -> 3.71
    end

    velocity = :math.sqrt(2 * gravity * distance)

    cond do
      velocity == 0 -> :stable
      velocity < 5 -> :slow
      velocity >= 5 and velocity < 10 -> :moving
      velocity >= 10 and velocity < 20 -> :fast
      velocity >= 20 -> :speedy
    end
  end

end

This time, the cond construct returns a value (an atom describing the velocity) based on the many guards it includes. Because that value is the last thing returned within the function, that becomes the return value of the function.

The results are a little different from our past trials:

iex(6)> r(Drop)
warning: redefining module Drop (current version defined in memory)
  lib/drop.ex:1

{:reloaded, Drop, [Drop]}
iex(7)> Drop.fall_velocity(:earth, 20)
:fast
iex(8)> Drop.fall_velocity(:moon, 20)
:moving
iex(9)> Drop.fall_velocity(:mars, 20)
:fast
iex(10)> Drop.fall_velocity(:earth, 30)
:speedy

If you want to capture the value produced by the cond construct in a variable, you can. Just replace the cond do in the first line with something like description = cond do.

Note

Elixir evaluates the cond and if statements on the basis of truthiness. All values are considered to be true except nil and false.

if, or else

For simpler cases, Elixir also offers an if function that tests only a single clause, and allows an else to follow if a failed test also requires action.

Example 4-5, in ch04/ex5-if, sends a warning to standard output (in this case IEx) if you drop an object too fast. It uses the simpler cousin of cond, if, to decide whether to put out the extra message.

Example 4-5. Sending an extra warning if the velocity is too high
defmodule Drop do

  def fall_velocity(planemo, distance) when distance >= 0 do
    gravity = case planemo do
     :earth -> 9.8
     :moon  -> 1.6
     :mars  -> 3.71
    end

   velocity = :math.sqrt(2 * gravity * distance)

    if velocity > 20 do
      IO.puts("Look out below!")
    else
      IO.puts("Reasonable...")
    end

   velocity

  end

end

The new if clause checks the velocity variable to see if it’s above 20. If it is, it calls IO.puts, which creates a side effect: a message on the screen. If not, the else clause puts a milder message on the screen (the velocity at the end makes sure that the calculated result is the return value):

iex(1)> Drop.fall_velocity(:earth, 50)
Look out below!
31.304951684997057
iex(2)> Drop.fall_velocity(:moon, 100)
Reasonable...
17.88854381999832

You can write if statements in a few different ways. If the if statement is compact enough, it can be tempting to put it on a single line:

iex(3)> x=20
20
iex(4)> if x>10 do :large end
:large

That works well, and you can even add an else:

iex(5)> if x>10 do :large else :small end
:large

As an alternative, Elixir lets you put a colon after the do and then use a shorter form:

iex(6)> if x>10, do: :large, else: :small
:large

You may also find Elixir’s unless statement more readable than an if when you want to test against an opposite:

iex(7)> unless x>10, do: :small, else: :large
:large

Variable Assignment in case and if Constructs

Every possible path created in a case, cond, or if statement has the opportunity to bind values to variables. This is usually a wonderful thing, but it can let you create unstable programs by assigning different variables in different clauses. This might look something like Example 4-6, which you can find in ch04/ex6-broken.

Example 4-6. A badly broken cond construct
defmodule Broken do

  def bad_cond(test_val) do

    cond do
      test_val < 0 -> x=1
      test_val >= 0 -> y=2
    end

   x+y

  end
end

The Elixir compiler warns you about this sort of questionable behavior and suggests how you can rewrite it. The output has been reformatted to fit the page:

$ iex -S mix
Erlang/OTP 19 [erts-8.0] [source] [64-bit] [smp:4:4] [async-threads:10] [hipe]
 [kernel-poll:false]

Compiling 1 file (.ex)

warning: the variable "x" is unsafe as it has been set inside a 
case/cond/receive/if/&&/||. Please explicitly return the variable value instead. 
For example:

    case int do
      1 -> atom = :one
      2 -> atom = :two
    end

should be written as

    atom =
      case int do
        1 -> :one
        2 -> :two
      end

Unsafe variable found at:
  lib/broken.ex:10

;; similar warning for variable "y"
Generated broken app
Interactive Elixir (1.3.1) - press Ctrl+C to exit (type h() ENTER for help)
iex(1)>

If you decide to ignore the warnings and insist upon using the broken function, you will get an error at runtime:

iex(1)> Broken.bad_cond(20)
** (ArithmeticError) bad argument in arithmetic expression
    (broken) lib/broken.ex:10: Broken.bad_cond/1
Note

Elixir also lifts Erlang’s tight rules on what can happen in the clause being evaluated by if and cond. Erlang only lets you use the features available in guards, ensuring that there will be no side effects. Elixir doesn’t have those limits.

The Gentlest Side Effect: IO.puts

Up until Example 4-5, all of our Elixir examples focused on a single path through a group of functions. You put an argument or arguments in, and got a return value back. That approach is the cleanest way to do things: you can count on things that worked before to work again because there’s no opportunity to muck up the system with leftovers of past processing.

Example 4-5 stepped outside of that model, creating a side effect that will linger after the function is complete. The side effect is just a message that appears in the shell (or in standard output when you start running Elixir outside of the shell). Applications that share information with multiple users or keep information around for longer than a brief processing cycle will need stronger side effects, like storing information in databases.

Elixir best practice suggests using side effects only when you really need to. An application that presents an interface to a database, for example, really will need to read from and write to that database. An application that interacts with users will need to put information on the screen (or other interface) so that users can figure out what they’re expected to do.

Side effects are also extremely useful for tracing logic when you are first starting out. The simplest way to see what a program is doing, before you’ve learned how to use the built-in tracing and debugging tools for processes, is to have the program report its status at points you consider interesting. This is not a feature you want to leave in shipping code, but when you’re getting started, it can give you an easily understandable window into your code’s behavior.

The IO.puts function lets you send information to the console, or, when you’re eventually running code outside of the console, to other places. For now, you’ll just use it to send messages from the program to the console. Example 4-5 showed the simplest way to use IO.puts, just printing a message it takes in double quotes:

IO.puts("Look out below!")

IO.puts adds a newline to the end, telling the console to start any new messages it sends at the beginning of the next line. This makes your results look a bit neater. If you don’t want a newline, you can use IO.write instead. If you want to print a variable that isn’t a string, you can use IO.inspect.

Note

Elixir flatly prohibits operations that could cause side effects in guard expressions. If side effects were allowed in guards, then any time a guard expression was evaluated—whether it returned true or false—the side effect would happen. IO.puts wouldn’t likely do anything terrible, but these rules mean that it too is blocked from use in guard expressions.

Simple Recursion

The main tool you’ll use to repeat actions is recursion: having a function call itself until it’s (hopefully) reached a conclusion. This can sound complicated, but it doesn’t have to be.

There are two basic kinds of useful recursion. In some situations, you can count on the recursion to reach a natural end. The process runs out of items to work on or reaches a natural limit. In other situations, there is no natural end, and you need to keep track of the result so the process will end. If you can master these two basic forms, you’ll be able to create many more complex variations.

Note

There is a third form, in which the recursive calls never reach an end. This is called an infinite loop and is best known as an error you’ll want to avoid. As you’ll see in Chapter 9, though, even unending recursion can be useful when you want to continually receive messages from a process.

Counting Down

The simplest model of recursion with a natural limit is a countdown, like the one used for rockets. You start with a large number and count down to zero. When you reach zero, you’re done (and the rocket takes off, if there is one).

To implement this in Elixir, you’ll pass a starting number to an Elixir function. If the number is greater than zero, it will then announce the number and call itself with the number minus one as the argument. If the number is zero (or less), it will announce blastoff! and end. Example 4-7, found in ch04/ex7-countdown, shows one way to do this.

Example 4-7. Counting down
defmodule Count do

  def countdown(from) when from > 0 do
    IO.inspect(from)
    countdown(from-1)
  end

  def countdown(from) do
    IO.puts("blastoff!")
  end

end

The last clause could have a guard—when from <= 0—but it would be useful only to make it clear to human readers when the blastoff happens . Unnecessary guard clauses may lead to later confusion, so brevity is probably the best option here. However, you’ll get a warning that from is unused in the final clause. Here’s a test run:

$ iex -S mix
Erlang/OTP 19 [erts-8.0] [source] [64-bit] [smp:4:4] [async-threads:10] [hipe]
 [kernel-poll:false]

Compiling 1 file (.ex)
warning: variable from is unused
  lib/count.ex:8

Generated count app
Interactive Elixir (1.3.1) - press Ctrl+C to exit (type h() ENTER for help)
iex(1)> Count.countdown(2)
2
1
blastoff!
:ok

The first time through, Elixir chose the first clause of countdown(from), passing it a value of 2. That clause printed 2, plus a newline, and then it called the countdown function again, passing it a value of 1. That triggered the first clause again. It printed 1, plus a newline, and then it called the countdown function again—this time passing it a value of 0.

The value of 0 triggered the second clause, which printed blastoff! and ended. After running three values through the same set of code, the function comes to a neat conclusion.

Note

You could also implement this conclusion with an if statement inside a single countdown(from) function clause, although this is unusual in Elixir. We find guards more readable in these cases, but you may see things differently.

Counting Up

Counting up is trickier because there’s no natural endpoint, so you can’t model your code on Example 4-7. Instead, you can use an accumulator. An accumulator is an extra argument that keeps track of the current result of past work, passing it back into a recursive function. (You can have more than one accumulator argument if you need, though one is often sufficient.) Example 4-8, which you can find in ch04/ex8-countup, shows how to add a countup() function to the count module. This function lets Elixir count up to a number.

Example 4-8. Counting up
defmodule Count do

  def countup(limit) do
    countup(1,limit)
  end

  defp countup(count, limit) when count <= limit do
    IO.inspect(count)
    countup(count+1, limit)
  end

  # use underscore to avoid "unused variable" warnings
  
  defp countup(_count, _limit) do
    IO.puts("finished!")
  end

end

It produces results like the following:

iex(1)> Count.countup(2)
1
2
finished!
:ok

The countup/2 function, which does most of the work, remains private and is not exported. This isn’t mandatory—you might make it public if you wanted to support counting between arbitrary values—but it’s a common practice. Keeping the recursive internal functions private makes it less likely that someone will misuse them for purposes they’re not well suited to. In this case, it doesn’t matter at all, but it can make a big difference in other more complex situations, especially when data is modified.

When you call countup/1, it calls countup/2 with an argument of 1 (for the current count) and the limit value you provided for the upper limit.

If the current count is less than or equal to the upper limit, the first clause of the countup/2 function reports the current count value with IO.puts. Then it calls itself again, increasing the count by one but leaving the limit alone.

If the current count is greater than the upper limit, it fails the guard on the first clause, so the second clause kicks in: it reports "Finished." and is done.

Warning

The guards here are sufficient to avoid infinite loops. You can enter zero, negative numbers, or decimals as arguments to countup/1 and it will terminate neatly. You can get into serious trouble, however, if your termination test relies on == or === for comparison to a single value rather than >= or <= for comparison to a range.

Recursing with Return Values

The counting examples we’ve seen so far are simple—they demonstrate how recursion works, but just discard the return values. There are return values—the IO.puts calls return the atom :ok—but they aren’t of much use. More typically, a recursive function call will make use of the return value.

A classic recursive call calculates factorials. A factorial is the product of all positive integers equal to or less than the argument. The factorial of 1 is 1; 1 by itself yields 1. The factorial of 2 is 2; 2 × 1 yields 2. It starts to get interesting at 3, where 3 × 2 × 1 is 6. At 4, 4 × 3 × 2 × 1 is 24, and the results get rapidly larger with larger arguments.

There was a pattern to that, though. You can calculate the factorial of any integer by multiplying the integer by the factorial of one less than that integer. That makes it a perfect case for using recursion, using the results of smaller integers to calculate the larger ones. This approach is similar to the countdown logic, but instead of just counting, the program collects calculated results. That could look like Example 4-9, which you’ll find in ch04/ex9-factorial-down.

Example 4-9. A factorial written with the counting-down approach
defmodule Fact do

  def factorial(n) when n > 1 do
    n * factorial(n - 1)
  end

  def factorial(n) when n <= 1 do
    1
  end
end

The first clause of factorial, used for numbers greater than 1, uses the pattern previously described. It returns a value that is the number, n, times the factorial of the next integer down. The second clause returns the value 1 when n reaches 1. Using <= in that comparison, rather than ==, gives the function more resilience against non-integer or negative arguments, though the answers it returns aren’t quite right: factorials really only work for integers of 1 or higher. The results are as previously suggested:

iex(1)> Fact.factorial(1)
1
iex(2)> Fact.factorial(3)
6
iex(3)> Fact.factorial(4)
24
iex(4)> Fact.factorial(40)
815915283247897734345611269596115894272000000000

This works, but it may not be clear why it works. Yes, the function counts down and collects the values, but if you want to see the mechanism, you need to add some IO.puts calls into the code, as shown in Example 4-10. (You can find this in ch04/ex10-factorial-down-instrumented.)

Example 4-10. Looking into the factorial recursion calls
defmodule Fact do

  def factorial(n) when n > 1 do
    IO.puts("Calling from #{n}.")
    result = n * factorial(n - 1)
    IO.puts("#{n} yields #{result}.")
    result
  end

  def factorial(n) when n <= 1 do
    IO.puts("Calling from 1.")
    IO.puts("1 yields 1.")
    1
  end
end

There’s a bit more overhead here. To present the result of the recursive call and still return that value to the next recursive call requires storing it in a variable, here called result. The IO.puts call makes visible which value produced the result. Then, because the last value expression in a function clause is the return value, result appears again. The second clause, for 1, is similar, except that it can report simply that 1 yields 1. because it always will.

When you compile this and run it, you’ll see something like the following:

iex(1)> Fact.factorial(4)
Calling from 4.
Calling from 3.
Calling from 2.
Calling from 1.
1 yields 1.
2 yields 2.
3 yields 6.
4 yields 24.
24

Although the calls count down the values, as the function logic would suggest, the messages about results don’t appear until the countdown is complete, and then they all appear in order, counting up.

The reason this happens is that the function calls don’t return values until the countdown is complete. Until then, Elixir builds a stack of frames corresponding to the function calls. You can think of the frames as paused versions of the function logic, waiting for an answer to come back. Once the call with an argument of 1 returns a simple value, not calling any further, Elixir can unwind those frames and calculate the result. That unwinding presents the results—“X yields Y.”—in the order that the frames unwind.

That “unwinding” also means that the code in Examples 4-9 and 4-10 is not tail recursive. When Elixir encounters code that ends with a simple recursive call, it can optimize the handling to avoid keeping that stack of calls around. This probably doesn’t matter for a one-time calculation, but it makes a huge difference when you write code that will stay running for a long time.

You can achieve tail recursion for factorials by applying the counting-up approach to factorials. You’ll get the same results—at least for integer values—but the calculations will work a little differently, as shown in Example 4-11 (in ch04/ex11-factorial-up).

Example 4-11. A factorial written with the counting-up approach
defmodule Fact do

  def factorial(n) do
    factorial(1, n, 1)
  end

  defp factorial(current, n, result) when current <= n do
    new_result = result * current
    IO.puts("#{current} yields #{new_result}.")
    factorial(current + 1, n, new_result)
  end

  defp factorial(_current, _n, result) do
    IO.puts("finished!")
    result
  end

end

As in the counting-up example, the main function call (here, factorial/1) calls a private function, factorial/3. In this case, there are two accumulators. current stores the current position in the count, whereas result is the answer from the previous multiplication. When the value of current climbs past the limiting value n, the first guard fails, the second clause is invoked, and the function is finished and returns the result. (To avoid a compiler warning, we precede the accumulator variables current and n with an underscore, because the final clause doesn’t use them.)

Because factorial/3’s last call in the recursive section is to itself, without any complications to track, it is tail recursive. Elixir can minimize the amount of information it has to keep around while the calls all happen.

The calculation produces the same results, but does the math in a different order:

iex(1)> Fact.factorial(4)
1 yields 1.
2 yields 2.
3 yields 6.
4 yields 24.
finished!
24

Although the code is tracking more values, the runtime has less to do. When it finally hits the final result, there’s no further calculation needed. That result is the result, and it passes back through to the original call. This also makes it easier to structure the IO.puts calls. If you remove them or comment them out, the rest of the code stays the same.

Get Introducing Elixir, 2nd Edition now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.