Why is factorial recursive function less efficient than a normal factorial function?

Question

I've got two functions that calculate the factorial of a number n. I can't see why the 'normal' function needs less time to calculate the factorial of a number n. This is the normal function:

double factorial(int n) {
    double s = 1;
    while (n > 1) {
        s *= n;
        --n;        
    }

    return s;
}

And this is the recursive function:

double factorial(int n) {
    if (n < 2) return 1;
    return n * factorial(n-1);
}

Which should be less time-consuming as it doesn't create a new variable, and it does less operations. While it is true that the normal function uses a little bit more of memory, it is faster.

Which one should I use and why?

PS: I'm using double as I needed it to calculate the Taylor series of e^x.

Answer 1

You write that the recursive function “should be less time-consuming as it doesn't create a new variable, and it does less operations”. The first assertion is pretty meaningless. Memory for local variables is typically allocated by a single subtraction operation, upon entering the function, and this takes insignificant time (it’s the fastest allocation known to man). The second assertion is just plain false for your C++ implementation. Since you have measured that the recursive function, with your compiler, is slower, it follows that it does more, not less.

Now, why.

Well, each call has to copy a return address and the actual arguments on the stack. This takes time. In addition, in order to support debugging and exceptions, each function call typically does some extra work establishing a nice stack frame, essentially storing information about how the stack was before the call.

A recursive variant does however not have to be slower. But almost paradoxically, a variant that in practice can be as fast as the iterative one, will appear to do more… The idea is to write it so that the compiler can transform it to an iterative version, that is, so that the compiler can replace the recursive call (which takes time) with simple looping.

The only problem is that as far as I know, very few if any C++ compilers do this kind of optimization. :-(

However, for completeness, the idea is to make sure that there is only one recursive call, and that it's the very last thing that happens. That's called tail recursion. Your current recursive code,

double factorial( int n )
{
    if( n < 2 ) { return 1; }
    return n*factorial( n-1 );
}

is not tail-recursive, because after the recursive call there is multiplication by n.

To make it tail-recursive you can pass as arguments the information necessary to do the thing that should be done at end, here *n. The information needed for that is the value of n, plus the fact that it should be done. This means introducing a helper function with suitable formal argument:

double factorialScaledBy( double m, int n )
{
    if( n < 2 ) { return m*1; }

    // Same as "n*factorialScaledBy( m, n-1 )", but tail-recursive:
    return factorialScaledBy( n*m, n-1 );  
}

double factorial( int n )
{
    return factorialScaledBy( 1, n );
}

Now a sufficiently smart compiler can notice that nothing more happens in the function execution after the recursive call, hence local variables are not used, hence they can just be reused for the recursive call, which therefore can be implemented as just simulated argument passing plus a jump back to the top of the function, i.e. a loop.

Cheers & hth.,

Answer 2

Your best bet is to not calculate the factorials explicitly at all. If you are computing a Taylor (Maclaurin) series of exp(x):

   exp(x) = 1 + x/1! + x^2/2! + x^3/3! + x^4/4! + ...

Your best bet is to do something like the following:

   double y = 1.0;
   int i = 1;
   double curTerm = 1.0;
   double eps = 1e-10;  // whatever's desired
   while( fabs(curTerm) > eps)
   {
        curTerm *= x / (double)i;
        y += curTerm;
        ++i;
   }

This way you never have to explicitly compute the factorials which will grow too quickly to be useful for this problem.

Answer 3

I would say this is because a function call is more expensive in time than a while loop. i would use the first (no recursive) as if the N is very big, you'll fill up your stack and might get a "stack overflow" :)

Answer 4

This certainly has to do with data structures. Data structures are funny things. Some of them perform great for smaller data sizes while some perform better for larger data sizes.

In the recursive code, there is a call stack with the entire contents of the current recursion being pushed to a stack and being fetched on the way back. This is an extra overhead of a function call on each recursive call. That is why, the performance is slow.

See this for more details: http://publib.boulder.ibm.com/infocenter/iadthelp/v6r0/topic/com.ibm.etools.iseries.pgmgd.doc/c0925076137.htm