0

This function has some problems ? 

 unsigned long factorial(unsigned long m)
 {
     return (m == 0) ? 1 : m * factorial(m - 1);
 }

If I add another function: 

  int myCombina(int q, int p)
  {
      return factorial(q) / ( factorial(q) * factorial(q-p) );
  }

This myCombina() is not efficient because a greatest common divisor should be cancelled in it to find combinatorial.

max(factorial(q), factorial(q-p)) can be cancelled out. We only need to compute q x (q-1) ... x (q -k +1).

Are there other problems ?

Any comments are welcome.

Thanks

dtustudy68
  • 325
  • 1
  • 4
  • 13
  • In any language that doesn't support *tail-call optimization*, a recursive implementation of factorial will also be extremely inefficient. An iterative solution will use only O(1) temporary storage, and will usually run considerably faster. – Daniel Pryden Oct 17 '11 at 21:36
  • The apparent language is C/C++ so tail call optimizations are supported. http://stackoverflow.com/questions/34125/which-if-any-c-compilers-do-tail-recursion-optimization – gkuan Oct 17 '11 at 21:38
  • @DanielPryden: Actually, it's O(log m) storage if you use a bignum type. – Marcelo Cantos Oct 17 '11 at 21:43
  • 1
    @gkuan: "supported" is not the same as "guaranteed". No self-respecting C or C++ programming would rely on unbounded recursion in production code (unless the depth is, say, O(log n)). – Marcelo Cantos Oct 17 '11 at 21:44
  • @DanielPryden *tail-call optimization* is as much a language feature as a feature of the code, and in this particular case it cannot be applied (if you return `m*factorial(m-1)` the call must return before the multiplication can be done, which means that the recursion cannot be converted to a loop. Now, if it was converted to allow the optimization (pass an extra argument with the temporary result) then the compiler can perform the optimization. – David Rodríguez - dribeas Oct 17 '11 at 21:48

3 Answers3

8

if m is very large, it may have stack overflow.

A stack overflow is not the main problem with your code... if m is very large you will get an integer overflow before you get a stack overflow.

You need to use some sort of Bignum type if you want this to work for m larger than about 12 (depending on the size of unsigned long on your platform).

Mark Byers
  • 811,555
  • 193
  • 1,581
  • 1,452
2

It is not written in tail recursive form so even if the compiler supports proper tail call optimization, you won't get the benefit.

gkuan
  • 921
  • 6
  • 6
  • huh? why not? how do you think a tail recusrive form would look like? – Karoly Horvath Oct 17 '11 at 21:41
  • I don't see how that link answers my question. the OP's code looks perfectly tail call optimizable. – Karoly Horvath Oct 17 '11 at 21:43
  • When tail call optimizations are taken into account, a recursive version can be just as fast as the iterative version. This example should not be a blanket example of why recursion should be avoided in all cases. – gkuan Oct 17 '11 at 21:44
  • 2
    This version is not tail recursive because it recursively calls factorial and then still has to multiple that result with m. Thus, it cannot be turned into a loop as is. Tail call position means that the last thing any recursive call does is the recursive call and not some other operation. – gkuan Oct 17 '11 at 21:45
  • @yi_H: That link answers precisely the question you asked. The accepted answer presents two recursive factorial functions and explains very clearly why one is tail-recursive and the other isn't. – Marcelo Cantos Oct 17 '11 at 21:49
  • surely it can be turned into a loop and it's easy to write the equivalent non-recursive method. a really clever compiler *could* do that. are you saying that modern compilers *actually* don't do that? are we arguing about theoretical vs practical? – Karoly Horvath Oct 17 '11 at 21:51
  • @Marcelo Cantos: yes, I know scheme (and I love SICP)... but that code *is* scheme, where the optimization is limited by the nature of the language.. – Karoly Horvath Oct 17 '11 at 21:55
  • @yi_H: *surely it can be turned into a loop*, of course it can when you know the domain, but most compilers will not be able to optimize that, not in scheme not in C++. The problem is that the code requires maintaining the state of all the recursive calls while it goes deeper into recursion, and only as it starts completing it can pull them away. `factorial(10)` needs to store `10,9,8,7,6,5,4,3,2,1` before it can start building the solution, and it is that intermediate step what inhibits the optimization, as the algorithm requires O(N) memory, and it just cannot do it. – David Rodríguez - dribeas Oct 17 '11 at 22:08
  • ... if you transform it into `long fact( long n, long acc ) { return n == 0 ? acc : fact( n-1, acc*n ) }` then the space requirement becomes O(1), it does not need to keep track of all the intermediate values, only of the accumulated temporary. Now it is trivial to transform into a loop without any knowledge of the domain, and that is what is called *tail-recursive*. If you want more information, I suggest that you google/check wikipedia for tail-recursion. – David Rodríguez - dribeas Oct 17 '11 at 22:11
2

The function can actually cause an stack overflow (each level of recursion will consume a bit of the stack until it get's all consumed).

As others have mentioned, you can convert the recursive function into a loop, which in this case would be simple, or you can modify the recursion to allow for tail-call optimization (have the compiler transform the recursion into a loop).

Just for the sake of it, to transform into a tail recursive call, the last statement of the function must be a return with the result obtained from the recursive call. Your code cannot be optimized away because your return statement contains m*factorial(n-1), that is, you don't return the value of the recursion, but actually operate on it before returning.

The transformation to make it tail recursive require pushing the multiplication down to the recursive call, and that is usually performed as an extra argument that keeps the temporary result:

unsigned long factorial_tail_recursive( 
                        unsigned long n,           // number to calculate factorial
                        unsigned long temp_result  // accumulated result
                      ) 
{
   return n == 0? tmp_result 
                : factorial_tail_recursive( n-1, n*temp_result );
}

// syntactic sugar to offer the same interface
unsigned long factorial( unsigned long n ) {
   return factorial_tail_recursive( n, 1 );    // accumulated result initialized to 1
}

But then again, for that particular problem an efficient iterative solution is probably easier to get right. Just maintain the accumulated result in a temporary variable and loop until the argument is reduced to 1.

David Rodríguez - dribeas
  • 204,818
  • 23
  • 294
  • 489