Writing a method that takes an integer, and returns it's factorial
- May 20, 2017
Sometimes, when being interviewed for a job as a software developer, you’ll be asked a question such as “write a method that takes an integer as a parameter, and returns it’s factorial.”
For example, the factorial of 3 is represented as “3!”, which is calculated via 321, which equals 6. 4! is 432*1, which is 24, etc.
Putting aside whether these kinds of questions should be asked in an interview, if they’re asking you this, there’s a fairly high likelihood they’re asking for you to show that you understand recursion. If that’s the case, no problem, something like this will calculate the factorial:
let rec factorial n =
match n with
| 0 | 1 -> 1
| n when n > 0 && n <= 12 -> n * factorial (n - 1)
| _ -> failwith "Parameter n is out of the supported range. Must be between 0 and 12."This can be run in the F# interactive shell via:
> factorial 3;;
val it : int = 6But what if they want to find out whether you:
- Understand recursion, and…
- Know when you can avoid recursion, and just write simple methods instead.
Recursion is surprisingly hard for a lot of people to get their heads around. The cost of understanding a codebase is high enough, without adding complexity associated with recursion, so let’s avoid it when it make sense to do so.
In the case of this particular question, a signed integer is 32 bits, and supports values up to 2,147,483,647. The factorial of 12 is 479,001,600, and the factorial of 13 is 6,227,020,800, which exeeds the maximum value supported by int32, so if we have a method which returns an integer, we can only support up to the factorial of 12. Even if we were to use an unsigned integer, we’d still max out at 4,294,967,295, which is still less than the factorial of 13.
Incidentally, if we removed the range checks in the above method, and were to try and calculate the factorial of 13, we’d end with integer overflow issues, and end up with a value of 1,932,053,504, which is less than the factorial of 13.
Given our method can only return factorials up to 12, which ends up being 13 distinct values, why not use a lookup table instead:
let factorials = [ 1; 1; 2; 6; 24; 120; 720; 5040; 40320; 362880; 3628800; 39916800; 479001600 ]
let factorialWithLookup n =
match n with
| n when >= 0 && n <= 12 -> factorials.[n]
| _ -> failwith "Parameter n is out of the supported range. Must be between 0 and 12."Our lookup table can be calculated via Wolfram Alpha, or by using the original factorial function:
printf "let factorialLookup = [ 1"
[1..132 |> Seq.map factorial |> Seq.iter (fun x -> printf "; %i " x)
printfn " ]"Need to support higher factorials? If an an int64 (long) was used, factorials up to 20 could be supported. Do we then need to use recursion? Nope, use a 21 element int64 lookup table.
int128 (decimal) supports values up to 79,228,162,514,264,337,593,543,950,335, suporting up to the factorial of 27 … for that, use a 28 element int128 lookup table. It’ll use less than 4 KiB of memory.
If you really want a method which calculated the factorial, rather than using a lookup, without using recursion, you could use the higher-order function:
let factorialHigherOrder n =
match n with
| 0 | 1 -> 1
| n when n > 0 && n <= 12 -> [1..n] |> List.reduce (*)
| _ -> failwith "Parameter n is out of the supported range. Must be between 0 and 12."A good case for recursion is when it’s much more complex to write iterative code. For example, tree traversal techniques such as pre-order and post-order can be written both iteratively and recursively. In this case, people often use recursion because it results in a simpler solution.
Recursion can make things simpler in some cases, yet I believe it’s best to avoid it unless you’re getting a clear benefit over iteration (or in the case of factorials, lookup tables)
