why is this factorial recursive function inefficient?

Question

In the book "Think like a programmer", the following recursive function is said to be "highly inefficient" and I can't figure out why (the book does not explain). It doesn't seem like there are any unnecessary calculations being done. Is it because of the overhead of calling so many functions (well the same function multiple times) and thus setting up environments for each call to the function?

int factorial(int n) {
  if (n == 1) return 1;
  else return n * factorial(n-1);
}

Answer 1

It is inefficient in two ways, and you hit one of them:

It is recursive, instead of iterative. This will be highly inefficient if tail-call optimization is not enabled. (To learn more about tail-call optimization, look here.) It could have been done like this:

int factorial(int n)
{
    int result = 1;
    while (n > 0)
    {
        result *= n;
        n--;
    }
    return result;
}

or, alternatively, with a for loop.

However, as noted in comments above, it doesn't really matter how efficient it is if an int can't even hold the result. It really should be longs, long longs, or even big-ints.

The second inefficiency is simply not having an efficient algorithm. This list of factorial algorithms shows some more efficient ways of computing the factorial by decreasing the number of numerical operations.