Factorial

The factorial of a non-negative integer, for instance n, is denoted by n! (read "n - factorial"). The result is the product of n and all the natural numbers below it. By convention, the factorial of 0 is 1, according to the empty product. Here is a table of the first ten positive integers and their factorials.

Directions

Given a positive integer (n), return the result of n!.

Examples

iex(1)> Factorial.factorial(1)
1
iex(2)> Factorial.factorial(5)
120
iex(3)> Factorial.factorial(25)
15511210043330985984000000

Constraints

Assume that n will be a positive integer from 1..1,000.

Note

Attempt to solve the problem by yourself. Spend approximately 10 minutes coming up with an original solution. There is nothing gained by copy /pasting someone else's solution or skipping straight to the answer. Create a new Elixir file and begin from a blank page. Start typing code, make comments about what you're trying to accomplish. Remember, try to break the problem down into smaller pieces and focus on solving one piece at a time. This is the best way to learn how to code. It will help you gain confidence in yourself and your abilities.

My approach

This problem is generally considered easy. It can be solved by as long as you know the definition of a factorial. Instead of thinking in terms of writing an algorithm that solves for all possible values of n , let's approach this problem by trying to solve for a specific input. I'll arbitrarily choose the number 4. We can write 4! in it's long form, 4 * 3 * 2 * 1. If we think about this in terms of recursion we can begin to develop a working solution. You should notice that for each multiplication we are multiplying n * n-1, this will be the core of our algorithm. If you look closely, it's really just the definition of a factorial.

# basic logic for solving a factorial
defmodule Factorial do
  def factorial(n) when n <= 1 do
    1
  end
end

This first function uses a guard clause to handle the cases of 0 and 1. Next, we'll write a function that solves for the input of numbers greater than 1:

 defmodule Factorial do
 # ... clipped for brevity

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

end

This second function is called when the input, n , is greater than 1. It multiplies n by a recursive call to n-1. Both of these functions can be written on a single line. Their order won't matter because only the function that satisfies the guard clause will execute.

# recursive approach to solving a factorial
defmodule Factorial do
  def factorial(n) when n <= 1, do: 1
  def factorial(n) when n > 1, do: n * factorial(n - 1)
end

The Factorial module above is now complete. It solves factorials and produces the correct results. Let's try it out:

iex)> Factorial.factorial(0)
1
iex)> Factorial.factorial(5)
120
iex)> Factorial.factorial(10)
3628800
iex)> Factorial.factorial(20)
2432902008176640000

Great, everything looks good. Although there is nothing wrong with the above solution, it would be considered a naive approach. The function is not optimized for performance. It is a recursive function but it has not been tail call optimized. A function can be made tail call recursive if the very last thing it does it call itself. To find out if a function is tail call recursive we must ask ourselves, "is the last line of execution a function call?". If we check the last line of execution in our factorial function (the part that comes after do:), we see n * factorial(n-1). The fact that we are performing a multiplication means that it is not tail call optimized. Let's rewrite the Factorial module using a tail call. Erlang will perform the optimization for us automatically, the only requirement is that our last line of execution must be a function call. In other words, we must remove that multiplication we perform before the recursive call.

In order to change the module and remove the multiplication from the recursive call, I'll will need to introduce an accumulator variable. To take advantage of this accumulator value, I'll add a helper function called "factorial_of". The main function that kicks off the execution will still be called "factorial". The accumulator value will initially start with a value of 1. Here is the first line:

defmodule Factorial do
  def factorial(n), do: factorial_of(n, 1)
# coming soon
# coming soon

end

When the "factorial" function is called, it will now call the helper function passing it both n and the starting accumulator value of 1. The next line will be the base case. It will stop the recursive call and return the answer, which will be stored in the accumulator variable. For now, let's skip the base case and check out how the helper function works.

defmodule Factorial do
  def factorial(n), do: factorial_of(n, 1)
# coming soon
  defp factorial_of(n, acc) when n > 0, do: factorial_of(n - 1, n * acc)

end

The helper function "factorial_of", is the core of the solution. The guard clause ensures we have a positive integer and we moved the multiplication into the function call. The last part of execution is now a function call. Erlang will automatically optimize this code. Lastly, we use the base case to stop the recursion and return the result.

# tail call optimized solution
defmodule Factorial do
  def factorial(n), do: factorial_of(n, 1)
  defp factorial_of(0, acc), do: acc
  defp factorial_of(n, acc) when n > 0, do: factorial_of(n - 1, n * acc)

end

Notice that the value of n is decremented in each recursive call. When it reaches 0, the answer is the accumulator. We now have a tail recursive function that is optimized for performance. We can test it out and be confident our function will perform correctly while passing in even higher values for n.

iex)> Factorial.factorial(0)
1
iex)> Factorial.factorial(10)
3628800
iex)> Factorial.factorial(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
iex)> Factorial.factorial(1000)
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000