# Factorials and recursive functions

• 09-01-2002
Factorials and recursive functions
One of the recent programs that was used as an example to help explain how a recursive function works used this program:

Code:

```#include <stdio.h> unsigned int f,x=0; unsigned int factorial(unsigned int a); int main(void) {         puts("Please enter an integer value from 1 and 8: ");         scanf("%d", &x);         if(x>8||x<1)         {                 puts("Only values from 1 to 8 are acceptable.");         }                 else         {                 f=factorial(x);                 printf("%u factorial equals %u\n\n", x,f);         }                 return 0; } unsigned int factorial(unsigned int a) {         if(a==1)         {                 return 1;         }         else         {                 a *=factorial(a-1);         }                 return a; }```
I understand how to get a factorial: 4=1*2*3*4 right but how does: a*=factorial(a-1) do that. As of yet I have figured that you are multiplying a to the function factorial(a-1) and assigning the value to a and returning it. I get lost right there, for one thing how do you use call a function within itself but with different arguments/parameters, and if doing that makes it different then how can you have that without declaring the prototype?
And finally I have not learned about factorials I just looked some stuff up on the net and that is how I found the forumla, could someone explain what the point of factorials are or even the point of a "recursive function".

I know this is a lot to ask so if someone could just answer one or two of them I would be grateful.

P.S. The program works just fine I just don't understand it.

Also if a moderator sees this can you tell me why I can no longer log in, I tried it with my user name: cap and my pass which I tried a few times and I know is correct but it keeps saying that I do not have the correct pass, I already e-mailed for my pass to be sent to me but I also wanted this question answered, thanks.
• 09-01-2002
Nick
One way you can think of is
factor(5) = 5 * factor(4)
factor(4) = 4 * factor(3)
factor(3) = 3 * factor(2)
factor(2) = 2 * factor(1)
factor(1) = 1 * factor(0)
factor(0) = 1
The factorial of 0 is defined to be 1.

Then putting together the functions
factor(5) = 5 * 4 * factor(3)
factor(5) = 5 * 4 * 3 * factor(2)
factor(5) = 5 * 4 * 3 * 2 * factor(1)
factor(5) = 5 * 4 * 3 * 2 * 1 * factor(0)
factor(5) = 5 * 4 * 3 * 2 * 1 * 1

Thinking recursively is similar to using induction. When you write
a factorial problem you are saying I know what the solution
is for n = 0 and I know what the solution is for n if I have
the factorial of n - 1. Your program then just puts together
the two facts. Most of the time a trace like this one is unnecessary.

Factorials are used for the number of permutations.
For example how many ways are there to choose a president
and vice president from a group of 5.

For the first person there are 5 different people. For the vice
president there are 4 different people since the president
has already been chosen. So the number of ways is 5 * 4. But
if you generalize the problem to choose "m different people from
n" people you will have
p(n, m) = n! / (n - m)!
• 09-01-2002
That helps a bit, can someone give an example(no code necessary)as to how you would use a recurssive function or factorial numbers in a real life situation?
• 09-01-2002
Crimpy
Quote:

That helps a bit, can someone give an example(no code necessary)as to how you would use a recurssive function or factorial numbers in a real life situation?
In real life situations a recursive solution isn't always best, in fact, any recursive program can be written as an iterative program sometimes with only a little extra work. The only time I use them are when there is a big time readability benefit. Factorials are useful in a lot of places, but I can't think of any really good examples except for permutations. How many combinations of a 5 letter word are there? The answer is !5 = 120, this can be very handy and I'll let you know how when I think of how. :)
• 09-01-2002
Nick
Just about every chess search function such as
minimax is recursive.

matrix multiplication algorithms such as straussens
are recursive

http://cs.engr.uky.edu/~lewis/essays.../Strassen.html

merge sort and quick sort are recursive.

Alot of this you would maybe design your algorithm recursively
then if there's a possible speedup you would do it
iteratively.
• 09-02-2002
Wow, I think I am going to have to get a math book, or at least go to the link you provided, lol. I was just asking because I couldn't think of any reason to check it over and over again, but at least I understand it a bit more, thanks again.
• 09-04-2002
Shiro
>can someone give an example(no code necessary)as to how
>you would use a recurssive function or factorial numbers in a
>real life situation?

The factorial of n can be calculated as:

n! = n * (n-1) * (n-2) * ... * 2 * 1

From this it can be seen that:

(n+1)! = (n+1) * n * (n-1) * (n-2) * ... * 2 * 1

In other words:

(n+1)! = (n+1) * n!

So:

n! = n * (n-1)!

This recursive definition can be put into a recursive function. The function must stop when k = 1, where k is a variable, and it starts with k = n.

Code:

```int main () {     int n;     int fac_n;     fac_n = fac (n);     return 0; } int fac (int k) {     if (k == 1) /* End step is reached */         return 1;     else         return (k * fac (k-1)); /* Recursion step */ }```
I hope it has explained a little bit.
• 09-16-2002
Sang-drax
• 09-16-2002
Hammer
>A more exotic way (and not that useful) of calculating factorials recursively:
It's also a C++ way, not C! :)

[EDIT]err... now you see it, now you don't ! :D