C Programming: How to Write a Recursive Function to Calculate Factorial?
Airfare Daily Deals eCigarettes Eyeglasses Hotels Jewelry Online Backup Online Dating Online Printing Online Tickets Skin Care Textbook Rentals Vitamins Web Hosting Weddings
Find thousands of shopping-related forums
SEARCH

C Programming: How to Write a Recursive Function to Calculate Factorial?

This article compares and contrasts between the non-recursive and recursive factorial calculation functions and shows how to write a recursive factorial function.

Earlier in these two articles - What is Recursion? How to Write a Recursive Function? Part 1 and What is Recursion? How to Write a Recursive Function? Part 2, we’ve gone through the concept of recursion. Then in another article C Programming: How to Write a Non-Recursive Function to Calculate Factorial? we discussed a non recursive function for calculating factorial of a number, so that we can contrast the non recursive solution with the recursive one in this article.

The factorial of a number is often expressed as n! (n followed by exclamation mark). Using the above notation, factorial of a number n can also be expressed as n * !(n-1), which essentially means that, factorial of a number n is n multiplied by factorial of (n-1). Since the factorial of a number can be expressed in terms of itself recursively, thus, factorial is a perfect candidate for recursion.

So, if the name of our factorial calculation function is rec_fact_func(), to calculate the factorial of a number stored in variable x, we would write function rec_fact_func(x), which would return rec_fact_func(x-1) * x. Here the function will keep on calling itself till the factorial of the number is calculated. If we do not write a conditional statement, to cover the corner cases of 1! and 0!, then the algorithm would “diverge” instead of converging towards the solution, and we’ll end up having an infinite recursion.

Thus, our factorial function should call itself with the argument as “previous argument” - 1, except when the argument is 0 or 1.

unsigned long rec_fact_func (unsigned int x)

{

if ( x <= 1 ) return 1;

return ( x * rec_fact_func (x-1) ); // recursive call - function calling itself

}

Notice the absence of else construct in the function definition. That’s because of the simple reason that if the condition would be true, the next statement would not be executed since the control would return from the body of the if structure itself. Thus, although, the else construct is missing, the return statement make for an effective logical if else structure.

This function, once invoked with a positive natural number x, (except x == 1) will call itself x - 1 times to calculate the factorial. Each call will take us one step closer to our final result.

Compare this solution with the loop construct of previous article. There we had an argument which stored the number, a counter (which also acted as current number in the series) and off course, the variable which iteratively got updated to finally store the result of calculating the factorial. Here, we simply have one variable, but this variable gets memory allocated for itself each time the function is invoked - in a new stack frame. Note that this means, we would allocate and deallocate x - 1 times (along with the stack frames)

Thus, this might be a good illustrative example to understand factorial, it is not an efficient solution. One should always be careful while choosing recursive algorithms over their non-recursive counterparts. Check out the screenshot for the complete program:

Need an answer?
Get insightful answers from community-recommended
experts
in Computer Programming & Languages on Knoji.
Would you recommend this author as an expert in Computer Programming & Languages?
You have 0 recommendations remaining to grant today.
Comments (0)
ARTICLE DETAILS
RELATED ARTICLES
ARTICLE KEYWORDS