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

There is significant function call overhead in C when not using a compiler that implements tail call optimization. — randomusername, Dec 12 '13 at 04:19
It uses O(n) stack space. However, given that 20! is well outside the range of a (32-bit) int, the claims of it being "highly inefficient" are dubious at best. — Yuushi, Dec 12 '13 at 04:19
@Yuushi comment is quite accurate. The best thing may be to keep a little of the dozen or factorials of interest. — Paul Draper, Dec 12 '13 at 04:21
@Yuushi Of course it is -- just add the (optional) `result` argument. — Tim Pierce, Dec 12 '13 at 04:22
@qwrrty Of course. However, how it is written **currently**, it isn't a tail call. — Yuushi, Dec 12 '13 at 04:22
@Yuushi : I suppose that's technically correct. But g++ does optimize it back into a loop. — Joe Z, Dec 12 '13 at 04:25
ZOMG: G++ 4.8.0 does something hilarious with the above code as compared to G++ 4.4.5. http://spatula-city.org/~im14u2c/dl/factorial-4.4.5.txt http://spatula-city.org/~im14u2c/dl/factorial-4.8.0.txt G++ 4.8.0 vectorized it??!? (Compiled with -O3) — Joe Z, Dec 12 '13 at 04:27
Note also that it is not correct. It does not give the correct answer for `n=0`, and does not terminate if `n<0`. — Keith, Dec 12 '13 at 04:27
@Keith give the OP some slack, he just wants to know why the book told him it was inefficient. — randomusername, Dec 12 '13 at 04:30
@chris : It can be inefficient with optimizations on too... G++ 4.8.0 unrolls and vectorizes this thing for no reason. (*See my link a couple comments back.) I can't imagine the result is actually efficient for reasonable values of `n`. — Joe Z, Dec 12 '13 at 04:30
@JoeZ Pfft - it unrolls and vectorizes to make it fast! Seriously though, [the assembly using `unsigned long long` is much more sane.](http://coliru.stacked-crooked.com/a/bc7d8b0afa84cfa6) — Casey, Dec 12 '13 at 04:36
@Casey : That's closer to what I got with the older compiler. Almost identical, save for the size of the types involved. — Joe Z, Dec 12 '13 at 04:37
@randomusername - Not bagging the OP at all, more the textbook. Don't see much point in discussing performance for code that does not work. The point being that elegance and possible compiler optimisations may all change should the code be made more robust. — Keith, Dec 12 '13 at 04:37
@Keith this is an easy fix though, just change the `==` to `<` or `<=` in the if statement and we're done. — randomusername, Dec 12 '13 at 04:40

score 7 · Accepted Answer · edited May 23 '17 at 11:57

7

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.

edited May 23 '17 at 11:57

Community

1
1

answered Dec 12 '13 at 04:25

Jashaszun

9,207
3
29
57

For me, `sizeof(long) == sizeof(int)`. – chris Dec 12 '13 at 04:36
1

`long` is typically a 32-bit integer, x86 or x64. Go `long long`. – Ed S. Dec 12 '13 at 04:38
@chris Well that completely depends on your C implementation. – Jashaszun Dec 12 '13 at 04:38
@Jashaszun, Yes, but it's pretty common. – chris Dec 12 '13 at 04:41
@chris Yeah, I agree. I edited my answer to account for Ed S.'s comment. – Jashaszun Dec 12 '13 at 04:42
Thanks. As a programmer, say for an open source program, can I pretty much assume that tail-call optimization is being used by whoever compiles the program? – Xu Wang Dec 12 '13 at 07:22

score 0 · Answer 2 · answered Dec 12 '13 at 04:20

0

There is significant function call overhead in C when not using a compiler that implements tail call optimization.

Function call overhead is the extra time and memory necessary for a computer to properly set up a function call.

Tail call optimization is a method of turning recursive functions like the one given into a loop.

answered Dec 12 '13 at 04:20

randomusername

7,927
23
50

1

-1 Can you elaborate? What kind of overhead is there? What is tail call optimization? – John Kugelman Dec 12 '13 at 04:23

score 0 · Answer 3 · edited Dec 12 '13 at 04:34

0

I think the book writer may want to tell readers to not abuse recursion. For this function you could just use:

int factorial(int n) {
    int res = 1; 
    for (i = 1; i <= n; i++) {
        res = res * i;
    }
    return res;
}

edited Dec 12 '13 at 04:34

Jashaszun

9,207
3
29
57

answered Dec 12 '13 at 04:27

yanchong

276
1
9

score 0 · Answer 4 · answered Dec 12 '13 at 04:50

Recursion is slower as well as memory eater in terms of Memory Stack.It is a time taking work to push info onto the stack and again to pop it .The main advantage of recursion is that it makes the algorithm a little easier to understand or more "elegant".

For finding the factorial we can use For loop that will be good in terms of memory as well as Time Complexity.

int num=4;
int fact = 1;
for (;num>1;num--)
{
fact = fact*num;   
}
//display fact

why is this factorial recursive function inefficient?

4 Answers4