The Inquisitive Developer

Learn With Me: Elixir - Factorial (#35)

Kevin Peter -

I'm going to take a break from learning Elixir to get some practice in using it. I created a project called Factorial, where I implement a factorial using Elixir. Like the FizzBuzz project, this is not anything impressive, but a simple project that will help me become more familiar with the language.

For those of you who can't remember what a factorial is (or never learned about it in the first place), it's the result of multiplying a series of ever-decreasing numbers until 1 is reached. In other words, the factorial of N is N * factorial(N - 1), which is the equivalent to N * (N - 1) * (N - 2) * ... * 2 * 1. So the factorial of 10 = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3,628,800. The factorial of 0 is defined as 1.

This just screams recursive algorithm at me, so that's what I implemented.

The Recursive Implementation

You can find the recursive implementation in the Factorial folder under the projects folder in the Learn With Me: Elixir repository on Github. It's in the "factorial_recursive.exs" file.

#Factorial implementation using standard recursion
defmodule Factorial do
	def of(0), do: 1
	def of(n) when n > 0, do: n * of(n - 1)
end

This is quite simple. The base case is represented by the function clause that pattern matches to 0. The factorial of 0 is always 1, so that's what is returned. The recursive case just multiplies the current number, "n" by the factorial of n - 1. Since a negative number would lead to infinite recursion, I thought it best to add a guard clause to keep that from happening. An error due to an out of bounds parameter is easy to spot and recover from, but a very long pause while the code recurses infinitely makes it a lot harder for the caller to find out what is going on.

I try to follow the Elixir convention of not going crazy with the guard clauses, but I think this one is well-justified, since it is much more developer friendly than a mysterious stop to code execution due to infinite recursion.

Here are some examples of using the function after loading it into IEx.

iex> Factorial.of(10)
3628800
iex> Factorial.of(1)
1
iex> Factorial.of(0)
1
iex> Factorial.of(-1)
** (FunctionClauseError) no function clause matching in Factorial.of/1

    The following arguments were given to Factorial.of/1:

        # 1
        -1

    projects/Factorial/factorial_recursive.exs:3: Factorial.of/1
iex> Factorial.of(1000)
4023872600770937735437024339230039857193748642107146325437999104299385123986290205920
4420848696940480047998861019719605863166687299480855890132382966994459099742450408707
3759918823627727188732519779505950995276120874975462497043601418278094646496291056393
8874378864873371191810458257836478499770124766328898359557354325131853239584630755574
0911426241747434934755342864657661166779739666882029120737914385371958824980812686783
8374559731746136085379534524221586593201928090878297308431392844403281231558611036976
8013573042161687476096758713483120254785893207671691324484262361314125087802080002616
8315102734182797770478463586817016436502415369139828126481021309276124489635992870511
4964975419909342221566832572080821333186116811553615836546984046708975602900950537616
4758477284218896796462449451607653534081989013854424879849599533191017233555566021394
5039973628075013783761530712776192684903435262520001588853514733161170210396817592151
0907788019393178114194545257223865541461062892187960223838971476088506276862967146674
6975629112340824392081601537808898939645182632436716167621791689097799119037540312746
2228998800519544441428201218736174599264295658174662830295557029902432415318161721046
5832036786906117260158783520751516284225540265170483304226143974286933061690897968482
5901254583271682264580665267699586526822728070757813918581788896522081643483448259932
6604336766017699961283186078838615027946595513115655203609398818061213855860030143569
4527224206344631797460594682573103790084024432438465657245014402821885252470935190620
9290231364932734975655139587205596542287497740114133469627154228458623773875382304838
6568897646192738381490014076731044664025989949022222176590433990188601856652648506179
9702356193897017860040811889729918311021171229845901641921068884387121855646124960798
7229085192968193723886426148396573822911231250241866493531439701374285319266498753372
1894069428143411852015801412334482801505139969429015348307764456909907315243327828826
9864602789864321139083506217095002597389863554277196742822248757586765752344220207573
6305694988250879689281627538488633969099598262809561214509948717012445164612603790293
0912088908694202851064018215439945715680594187274899809425474217358240106367740459574
1785160829230135358081840096996372524230560855903700624271243416909004153690105933983
8357779394109700277534720000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000

The factorial works as designed, and negative numbers result in an error. The factorial of 1000 results in an enormous number, which Elixir has no problem with. Calculating the factorial of 1000 didn't even result in a noticeable pause. IEx spit out that huge number in a fraction of a second.

The Optimized Recursive Implementation

I wasn't satisfied in just ending it there, so I went ahead and created another version that uses tail call optimization.

You can find the optimized implementation in the Factorial folder under the projects folder in the Learn With Me: Elixir repository on Github. It's in the "factorial_optimized.exs" file.

#Factorial implementation with tail call optimization
defmodule Factorial do
	def of(n), do: of(n, 1)
	defp of(0, current_factorial), do: current_factorial
	defp of(n, current_factorial) when n > 0, do: of(n - 1, current_factorial * n)
end

There's a public function that takes a number, which immediately calls the private function with an initial factorial. The private function has a base case clause and a recursive case clause. The factorial is calculated on the way into the call stack and passed onward as a parameter rather than calculated on the way out and passed back as a return value. This allows for tail call optimization because the recursive function call is the last thing the function does.

The current factorial parameter, which keeps track of the current factorial so far, is initialized at 1 in the initial call to the recursive private function.

Here's the output from calling the optimized version in IEx.

iex> Factorial.of(10)
3628800
iex> Factorial.of(1)
1
iex> Factorial.of(0)
1
iex> Factorial.of(-1)
** (FunctionClauseError) no function clause matching in Factorial.of/2

    The following arguments were given to Factorial.of/2:

        # 1
        -1

        # 2
        1

    projects/Factorial/factorial_optimized.exs:4: Factorial.of/2
Factorial.of(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

All these calls were instantaneous from my human sense of time, so I didn't notice any difference in performance, if there was any at all.

The Reduce Implementation

I can make this even easier by using Enum.reduce/2, which I covered in my previous post on Enum module functions. A reduce operation makes calculating a factorial even easier to understand. The Enum.reduce/2 function no doubt implements a very similar pattern to the one I used in implementing the tail call optimized factorial function, but in a way that is easy for us to plug in the data and function.

You can find the reduce implementation in the Factorial folder under the projects folder in the Learn With Me: Elixir repository on Github. It's in the "factorial_reduce.exs" file.

#Factorial implementation using a range and reduce
defmodule Factorial do
	def of(0), do: 1
	def of(n) when n > 0 do
		Enum.reduce(1..n, fn (x, fact) -> fact * x end)
	end
end

I create a range to represent the numbers that will be multiplied and a function that multiplies them and returns the factorial. The factorial is passed back as the accumulator value and passed to the next iteration of reduce.

I also had to create a special case clause when a 0 is passed in as a parameter. Passing 0 to the other function clause would create a descending range 1..0, which always results in the result being 0 when it should be 1.

When run in IEx, the results were the same as the previous implementations.

When looking over the code above, I noticed that the anonymous function I passed into reduce does the exact same thing as the built-in multiply function. When I saw that this was the case, I was able to simplify it even further.

#Factorial implementation using a range and reduce
defmodule Factorial do
	def of(0), do: 1
	def of(n) when n > 0 do
		Enum.reduce(1..n, &*/2)
	end
end

The multiply operator is also a function in the Kernel module, so I was able to use that to do the work. What you see above is about as simple as it gets. That's so much nicer than the tail call optimized recursive algorithm I wrote. I love the functions in the Enum module!