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

Improve this question
5
  • 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. Commented Oct 17, 2011 at 21:36
  • The apparent language is C/C++ so tail call optimizations are supported. stackoverflow.com/questions/34125/… Commented Oct 17, 2011 at 21:38
  • @DanielPryden: Actually, it's O(log m) storage if you use a bignum type. Commented Oct 17, 2011 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)). Commented Oct 17, 2011 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. Commented Oct 17, 2011 at 21:48

3 Answers 3

Reset to default
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).

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

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.

Improve this answer

9 Comments

huh? why not? how do you think a tail recusrive form would look like?
I don't see how that link answers my question. the OP's code looks perfectly tail call optimizable.
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.
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.
@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.
|
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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.