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.

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)!

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?

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. :)

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.

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.

>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.

>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