1
\$\begingroup\$

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 (n-1) ;

    }

}

int main() {

    int n;

    std::cin >> n;

    std::cout << factorial (n) ;

}

Is there a more efficient solution to this problem?

\$\endgroup\$
5
\$\begingroup\$

Yes, there is a more efficient solution that still uses recursion; specifically, using Tail Recursion.

When you return n * factorial(n-1);, the compiler can’t optimize the call away because it still has more work to do when the call to factorial(n-1) 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(n-1, n*product);
}

The difference between your implementation and a tail-recursive 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 tail-recursive algorithm uses only 1 stack frame, so it will return the (incorrect) answer of zero.

(Why zero? Assuming 32-bit 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 32-bits is zero. Any higher factorial is a multiple of 34!, so will also evaluate as zero.)

\$\endgroup\$
4
\$\begingroup\$

Well, first congratulations on successfully solving the Task.

Now, let's look at your solution:

  1. 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 non-whitespace really makes me want to re-indent.

  2. It's customary to end every line of output with a \n to play nice with the console. That doesn't mean you should treat \n as line-terminator instead of line-separator on input though.

  3. Your solution not being tail-recursive won't threaten to overflow the stack for a simple reason: Signed integer-Overflow is Undefined Behavior, and will happen far earlier.

    Still, consider converting to tail-recursion, 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);
    }
    
\$\endgroup\$
  • \$\begingroup\$ I always shy away from return cond ? value : func(value) in tail-recursion, since it isn’t clear that the compile will see that as if (cond) return value; else return func(value);. Any compiler worth it’s salt will see it as such, but for the student, they don’t see return func(value), they see, “evaluate the else path, and use that in the ?: expression, and return that”, which is not a tail-recursive construct. \$\endgroup\$ – AJNeufeld Jul 1 '18 at 23:53
  • \$\begingroup\$ @AJNeufeld: There is no guarantee the compiler can identify and take advantage of tail-recursion anyway. But if it can, that should really not pose any problem. \$\endgroup\$ – Deduplicator Jul 2 '18 at 1:03
  • \$\begingroup\$ You misunderstood. The problem is not the compiler. (Any compiler worth it’s salt will see it as such...) The problem is the student. For tail recursion to be possible, you need to directly return the result of the recursive call. Using the value of the recursive call in an ?:-expression muddies the water, leading the student to think using it in other expressions might be possible. \$\endgroup\$ – AJNeufeld Jul 2 '18 at 1:14
  • 1
    \$\begingroup\$ @AJNeufeld Maybe, but then the Student is easily unconfused, and is better for having encountered that (already). \$\endgroup\$ – Deduplicator Jul 2 '18 at 9:37
3
\$\begingroup\$

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(n-1);
}

For any compile time known input this will be calculated by the compiler.

\$\endgroup\$
0
\$\begingroup\$

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 non-portable.

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(n-1, 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);
}
\$\endgroup\$
  • \$\begingroup\$ 0 is a valid input to the factorial function, and 0! is defined to be 1. You can reason this by observing (n-1)! = n!/n, which leads to 0! = 1!/1 = 1. \$\endgroup\$ – AJNeufeld Jul 2 '18 at 20:12
  • \$\begingroup\$ But the problem states that “takes a positive integer”, which is more restricted. \$\endgroup\$ – JDługosz Jul 2 '18 at 20:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.