Chapter 4. Logic and Recursion
Étude 41: Using case
Change the area/3
function that you wrote in
Étude 32 so that it uses a case
instead
of pattern matching. Use a guard on the function definition to ensure
that the numeric arguments are both greater than zero.
Étude 42: Recursion
This is a typical exercise for recursion: finding the greatest common divisor (GCD) of two integers. Instead of giving Euclid’s method, we’ll do this with a method devised by Edsger W. Dijkstra. The neat part about Dijkstra’s method is that you don’t need to do any division to find the result. Here is the method.
To find the GCD of integers M and N:
 If M and N are equal, the result is M.
 If M is greater than N, the result is the GCD of M  N and N
 Otherwise M must be less than N, and the result is the GCD of M and N  M.
Write a function gcd/2
in a module named Dijkstra
that implements
the algorithm. This program is an ideal place to use Elixir’s cond
construct.
Here is some sample output.
iex(1)> c("dijkstra.ex") [Dijkstra] iex(2)> Dijkstra.gcd(2, 8) 2 iex(3)> Dijkstra.gcd(14, 21) 7 iex(4)> Dijkstra.gcd(125, 46) 1 iex(5)> Dijkstra.gcd(120, 36) 12
See a suggested solution in Appendix A. You can also use guards with multiple clauses to solve this étude; the solution for that approach is in Appendix A. In general, use of multiple clauses is considered more in the spirit of Elixir.
The next two exercises involve writing code to raise a number to an integer power (like 2.5^{3} or 4^{2}) and finding the nth root of a number, such as the cube root of 1728 or the fifth root of 3.2.
These capabilities already exist with the :math.pow/2
function, so you may
wonder why I’m asking you to reinvent the wheel. The reason is not to replace
:math.pow/2
, but to experiment with recursion by writing functions that can be
expressed quite nicely that way.
Étude 43: NonTail Recursive Functions
Create a module named Powers
(no relation to Francis Gary Powers), and
write a function named raise/2
which takes parameters x
and n
and
returns the value of x^{n}.
Here’s the information you need to know to write the function:
 Any number to the power 0 equals 1.
 Any number to the power 1 is that number itself — that stops the recursion.

When
n
is positive,x^{n}
is equal tox
timesx^{(n  1)}
— there’s your recursion. 
When
n
is negative,x^{n}
is equal to1.0 / x^{n}
Note that this algorithm is not tail recursive.
Warning
The Elixir kernel already has a raise/2
function, so your function will cause a conflict unless you add this after the defmodule
:
import Kernel, except: [raise: 2]
Here is some sample output.
iex(1)> c("powers.ex") \[Powers\] iex(2)> Powers.raise(5,1) 5 iex(3)> Powers.raise(2,3) 8 iex(4)> Powers.raise(1.2, 3) 1.728 iex(5)> Powers.raise(2, 0) 1 iex(6)> Powers.raise(2, 3) 0.125
If you try raising 0 to a negative power, you will get an error message. For now, just let the error occur. You will learn more about error handling in Chapter 10.
Étude 44: Tail Recursion with an Accumulator
Practice the “accumulator trick.”
Rewrite the raise/2
function for n
greater than zero so that it
calls a helper function raise/3
This new function has x
, n
, and
an accumulator
as its parameters.
Your raise/2
function will return 1 when n
is equal to 0,
and will return 1.0 / raise(x, n)
when n
is less than zero.
When n
is greater than zero, raise/2
will
call raise/3
with arguments x
, n
, and 1 as the accumulator
.
The raise/3
function will return the
accumulator
when n
equals 0 (this will stop the recursion).
Otherwise, recursively call raise/3
with x
, n  1
,
and x
times the accumulator
as its arguments.
The raise/3
function is tail recursive.
Warning
Because the kernel also contains a raise/3
function, you have to change
your import
as follows:
import Kernel, except: [raise: 2, raise: 3]
Étude 45: Recursion with a Helper Function
In this exercise, you will add a function nth_root/2
to the
Powers
module. This new function finds the
nth root of a number, where n is an integer.
For example, nth_root(36, 2)
will calculate
the square root of 36, and nth_root(1.728, 3)
will return the cube
root of 1.728.
The algorithm used here is the NewtonRaphson method for calculating roots. (See http://en.wikipedia.org/wiki/Newton%27s_method for details).
You will need a helper function nth_root/3
, whose parameters
are x
, n
, and an approximation to the result, which we
will call a
. nth_root/3
works as follows:

Calculate
f
as(a^{n}  x)

Calculate
f_prime
asn * a^{(n  1)}

Calculate your next approximation (call it
next
) asa  f / f_prime

Calculate the change in value (call it
change
) as the absolute value ofnext  a

If the
change
is less than some limit (say, 1.0e8), stop the recursion and returnnext
; that’s as close to the root as you are going to get. 
Otherwise, call the
nth_root/3
function again withx
,n
, andnext
as its arguments.
For your first approximation, use x / 2.0
. Thus, your nth_root/2
function
will simply be this:
nth_root(x, n) → nth_root(x, n, x / 2.0)
Use IO.puts
to show each new approximation as you
calculate it. If your argument name is estimate
, you would do something like this:
IO.puts("Current guess is #{estimate}")
Here is some sample output.
iex(1)> c("powers.ex") \[Powers\] iex(2)> Powers.nth_root(27, 3) Current guess is 13.5 Current guess is 9.049382716049383 Current guess is 6.142823558176272 Current guess is 4.333725614685509 Current guess is 3.3683535855517652 Current guess is 3.038813723595138 Current guess is 3.0004936436555805 Current guess is 3.000000081210202 Current guess is 3.000000000000002 3.0
Get Études for Elixir now with O’Reilly online learning.
O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.