Problem
Write a factorial function that takes a positive integer, N as a parameter and prints the result of N! (N factorial).
Note: If you fail to use recursion or fail to name your recursive function factorial or Factorial, you will get a score of 0 .
Here’s my solution in C++:
#include <iostream>
int factorial( int n ) {
if(n<=1)
return 1 ;
else{
return n * factorial (n1) ;
}
}
int main() {
int n;
std::cin >> n;
std::cout << factorial (n) ;
}
Is there a more efficient solution to this problem?
Solution
Yes, there is a more efficient solution that still uses recursion; specifically, using Tail Recursion.
When you return n * factorial(n1);
, the compiler can’t optimize the call away because it still has more work to do when the call to factorial(n1)
returns; it has to do the multiplication, and return the result.
If, instead, you ended the function with return factorial(arguments);
, the compiler can optimize away both the call and the return with a jump to the start of the factorial
function, with the new arguments. No additional stack frames are required. The arguments you need to pass would be the original argument(s) and any “running total”.
int factorial(int n, int product=1) {
if ( n <= 1 )
return product;
return factorial(n1, n*product);
}
The difference between your implementation and a tailrecursive one can be seen by trying to calculate factorial(1000000000)
. Your implementation will require 1 billion stack frames, which should likely crash the program. A tailrecursive algorithm uses only 1 stack frame, so it will return the (incorrect) answer of zero.
(Why zero? Assuming 32bit integer, 34! has 17 even numbers, 8 multiples of 4, 4 multiples of 8, 2 multiples of 16, and a 32, which means the answer is has 17+8+4+2+1=32 powers of 2. And any number multiplied by 2^32, modulo 32bits is zero. Any higher factorial is a multiple of 34!, so will also evaluate as zero.)
Well, first congratulations on successfully solving the Task.
Now, let’s look at your solution:

While whitespace is basically free, try to be consistent where you insert it. Before a semicolon is very odd and disconcerting, around binary operators is expected, but a whole free line between all lines containing any nonwhitespace really makes me want to reindent.

It’s customary to end every line of output with a
n
to play nice with the console. That doesn’t mean you should treatn
as lineterminator instead of lineseparator on input though. 
Your solution not being tailrecursive won’t threaten to overflow the stack for a simple reason: Signed integerOverflow is Undefined Behavior, and will happen far earlier.
Still, consider converting to tailrecursion, which the compiler can easily optimize to Iteration:
static int factorial_impl(int n, int r) { return n < 2 ? r : factorial_impl(n  1, r * n); } int factorial(int n) { return factorial_impl(n, 1); }
Actually this can be even faster at nearly compile Time. You should realize already, that factorial is a closed formula. So you can write:
constexpr int factorial(const int n) {
if (n <= 1)
return 1;
return n*factorial(n1);
}
For any compile time known input this will be calculated by the compiler.
The requirements stated “a positive integer”. You just used int
(whatever size that is) with no indication as to why that is big enough or how the actual limits imposed by this is nonportable.
At the very least, isolate this decision and use a named alias. That way, when the customer realizes that you gave him 32 bits and he really needs 64, you just change one line. Or if you realize that he meant arbitrary sized integers, you add an #include
and change that one line.
For the “you didn’t say so I used this” case, at least use a portable sized type so the behavior is the same across platforms.
That is:
using factorial_domain_t = std::uint32_t;
factorial_domain_t factorial_impl (factorial_domain_t n, factorial_domain_t q)
{
return (n==1) ? q : factorial_impl(n1, n*q);
}
factorial_domain_t factorial (factorial_domain_t n)
{
if (n <= 0) throw std::invalid_argument ("factorial function that takes a positive integer");
// or: use the `Expects` macro from gsl
return factorial_impl (n, 1);
}