Recursion

This is a discussion on Recursion within the C Programming forums, part of the General Programming Boards category; I'm having trouble understanding the following code fragment. Should it return 3 * 3=9 Code: #include <stdio.h> int factorial(int num); ...

  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,066
    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,066
    "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
    cwr
    cwr is offline
    Registered Luser cwr's Avatar
    Join Date
    Jul 2005
    Location
    Sydney, Australia
    Posts
    868
    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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21