Thread: Factorials and recursive functions

  1. #1
    SadGuy
    Guest

    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.

  2. #2
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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)!

  3. #3
    sadGuy
    Guest
    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?

  4. #4
    Registered User
    Join Date
    Jul 2002
    Posts
    66
    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.

  5. #5
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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.

  6. #6
    sadGuy
    Guest
    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.

  7. #7
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,380
    >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.

  8. #8
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  9. #9
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    >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 !
    Last edited by Hammer; 09-16-2002 at 03:40 AM.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Counting up(and down) using recursive function. Please help.
    By MarkSquall in forum C++ Programming
    Replies: 6
    Last Post: 06-06-2008, 04:26 AM
  2. factorials in recursive function
    By CBeginner in forum C++ Programming
    Replies: 4
    Last Post: 10-30-2002, 07:33 AM