Hackerrank Day 9: Recursion

Question

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?

Answer 1

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.)

Answer 2

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);
   }
   

Answer 3

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.

Answer 4

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);
}