Thread: Recursion

  1. #1
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335

    Recursion

    I'm having trouble understanding the following code fragment. Should it return 3 * 3=9
    Code:
    
    #include <stdio.h>
    int factorial(int num);
    void main()
    {
        int fact, num=3;
        fact = factorial(num);
        printf("%d factorial = %d\n", num, fact);
    }
    
    int factorial(int num)
    {
        /* num factorial. Assumes num >= 1 */
        if (num == 1) return 1;
        else return (num * factorial(num-1));
    }

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    847
    it should return 3*2*1. Try putting a printf function in the factorial function so you can see whats happening.
    Last edited by Quantum1024; 11-15-2005 at 03:47 AM.

  3. #3
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    i still don't understand it, i tried the iterated version:

    Code:
    
    #include <stdio.h>
    int factorial(int num);
    void main()
    {
        int fact, num=4;
        fact = factorial(num);
        printf("%d factorial = %d\n", num, fact);
    }
    
    int factorial(int num)
    {
        /* num factorial. Assumes num >= 1 */
        int i, fact=1;
        for (i=2; i<=num; i++)
        {
            fact *= i;
            printf("\n%d\n", i);
        }
        printf("\n");
        return fact;
    }
    but it doesn't add up:

    i = 2

    i = 3

    i = 4

    4 factorial = 24

    2*1(fact) = 2
    3*1(fact) = 5
    4*1(fact) = 10



    hmm?:|

  4. #4
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,079
    Four factorial is 24.

    ...that's what I got on the program.
    Sent from my iPadŽ

  5. #5
    Registered User
    Join Date
    Jan 2005
    Posts
    847
    A factorial is the result of multiplying a number by all number less then that number. Such as 4*3*2*1=24
    the for loop counts from 2 to the number who's factorial you want.
    Code:
     fact *= i;
    This line multiplies fact by i so the result of going thru the loop is
    i=2 fact*2=2
    i=3 fact*3=6
    i=4 fact*4=24
    Multiplyig by 1 has no affect so there is no need to start the loop with i equal to 1
    Last edited by Quantum1024; 11-15-2005 at 04:19 AM.

  6. #6
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    Yeah 1*2*3*4 = 24. I just don't get what fact *= i;
    does.
    To me it reads

    1*1= 1

    2*1 = 3 (incremented from previous value)

    3*1 = 6 (incremented from previous value)

    4 * 4 = 22 (incremented from previous value)

    why is it not 24?:|

  7. #7
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    Quantum,

    i=2 fact*2
    i=3 fact*3
    i=4 fact*4

    gives me 16.

  8. #8
    Registered User
    Join Date
    Jan 2005
    Posts
    847
    fact *= i; means to multiply fact by i and store the result in fact.

  9. #9
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,079
    "Fact *= i" is the equivilent of "Fact = Fact * i;"

    In otherwords

    fact = 1 * 4

    i - 1

    fact = 4 * 3

    i - 1

    fact = 12 * 2

    i - 1

    fact = 24 * 1

    fact = 24
    Sent from my iPadŽ

  10. #10
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    thanks guys, the *= expression confused me a bit, and the recursion bit made it even more confusing since i didn't understand the iterated version.

  11. #11
    Super Moderator Harbinger's Avatar
    Join Date
    Nov 2004
    Posts
    74
    > void main()
    And 200+ posts - tsk

  12. #12
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    Heh, i didn't write the code. It was from an example in a book. I know that void main is a big no no. Since when did post count equate to > knowledge?
    tsk.tsk.
    Last edited by Axel; 11-16-2005 at 10:25 PM.

  13. #13
    Registered Luser cwr's Avatar
    Join Date
    Jul 2005
    Location
    Sydney, Australia
    Posts
    869
    The theory is that if you've made 200 posts to this site, the chances are you've posted a program before, and if you used void main, you'd have been told off, and learned to not do it again.

  14. #14
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    nope, i don't believe i've used void main anywhere. Like i said it was specifically with this example. Thanks for your help everyone.

  15. #15
    Sr. Software Engineer filker0's Avatar
    Join Date
    Sep 2005
    Location
    West Virginia
    Posts
    235
    Just a quick addition to the commentary.

    The definition of factorial is recursive.
    For all whole numbers greater than 1, in algebraic notation: n! = n * ((n-1)!)
    By definition, 1! = 1

    So:
    Code:
          1! = 1
          2! = 2 * 1! = 2 * 1 = 2
          3! = 3 * 2! = 3 * 2 * 1! = 3 * 2 * 1 = 6
          4! = 4 * 3! = 4 * 3 * 2! = 4 * 3 * 2 * 1! = 4 * 3 * 2 * 1 = 24
          5! = 5 * 4! = 5 * 4 * 3! = 5 * 4 * 3 * 2! = 5 * 4 * 3 * 2 * 1! = 5 * 4 * 3 * 2 * 1 = 120
    and so on. You will note that all factorial values other than 1! are even.
    Insert obnoxious but pithy remark here

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 08:45 PM
  2. Recursion... why?
    By swgh in forum C++ Programming
    Replies: 4
    Last Post: 06-09-2008, 09:37 AM
  3. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 09:56 AM
  4. To Recur(sion) or to Iterate?That is the question
    By jasrajva in forum C Programming
    Replies: 4
    Last Post: 11-07-2001, 08:24 AM
  5. selection sorting using going-down and going-up recursion
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 11-02-2001, 01:29 PM
Website Security Test