Thread: Recursion

  1. #1
    Registered User
    Join Date
    May 2005
    Posts
    207

    Recursion

    I have a simple recursion program that I copied out of a book. It works fine, but I'm still having trouble understanding exactly what goes on during recursion. I tried inserting printf statements in my code to see what was going on, but it only confused me more... :-(

    Code:
    #include <stdio.h>
    
    long double factr (long double n);
    
    void main ()
    {
         long double highest;
    
         do
         {
               printf ("\n\nType '0' to quit.");
               printf ("\n\nPlease specify a max range to calculate factorials.\n");
               scanf ("%Lf", &highest);
    
               if (highest > 0)
               {
                      factr (highest);
               }
         } while (highest > 0);
    
         printf("\n\n");
         highest = 0;
    }
    
    long double factr (long double n)
    {
         long double answer;
    
         printf ("Start Recursion!  %d   %d\n", n, answer);
         if (n == 1) return (1);
         answer = n * factr (n-1);  //recursive call
         printf ("\n%g   %g", n, answer);
         return (answer);
    }
    What I don't understand is why the "Start Recursion!" prints before any calculations are made & how it's able to print out the correct answers!?

    mw
    Last edited by Lionmane; 06-01-2005 at 09:09 PM.

  2. #2
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    First things first - solve the errors
    printf ("Start Recursion! %d %d\n", n, answer);
    both n and answer are long doubles, but you're using %d in the format string sent to printf.
    %d are used to print integers. Use %lf instead.
    Second all code is executed sequentialy. When the printf is called n already as a value assigned, because it is a function argument, but answer hasn't because it's declared but not initialized. After that you calculate the value of answer. Only then can you call the printf function.

    factorials are integer operations, therefore long double is being missused. use unsigned int, unsigned long. If you do that then you must use %d as flag for the format function.

    About the recursion itself .. it very easy:
    7! = 7 * 6!
    6! = 6*5! -> 7! = 7 * 6 * 5!
    .. and so on
    but you could go on forever so there must be a case where you stop
    that when 0! = 1.
    0! doens't depend on any other factorial. yet 7! depends on 6!.

  3. #3
    Registered User
    Join Date
    May 2005
    Posts
    207
    Ok, I changed all of my "long double" to "unsigned long". I left the %d in my printf statement like you said (for use with "unsigned long").

    But now I get a "runtime error" after "Start Recursion!" gets to 1. If I click "ignore" it gives me another popup error "R6002 - floating point not loaded" & I click ignore again. Then it prints the same thing on my "dos" window & the program ends.

    I understand that "answer" is not initialized the FIRST time the function is called, but shouldn't it already be initialized for the recursive calls?

    I think I'm not understanding something about how recursion works... :-(

    mw

  4. #4
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    ups... yet its not very important if the numbers are below 2^31-1.. sorry !!
    %d is for signed integers. for unsigned use %u. also change %g with %u.

    Quote Originally Posted by Lionmane
    I understand that "answer" is not initialized the FIRST time the function is called, but shouldn't it already be initialized for the recursive calls?
    No because answer is a local variable, and a new one is created every time the function is called, recursively or not.
    You're considering that the variable is static. you can however declare it as static, because it won't afect the result.
    static unsigned long answer;
    Last edited by xErath; 06-01-2005 at 10:58 PM.

  5. #5
    Registered User
    Join Date
    May 2005
    Posts
    207
    A new variable is created everytime the function is called?! Ok, I understood this for regular function calling... But how does answer accumulate?!

    I don't seem to be understanding what's happening during a recursive call at all... :-(

    mw

  6. #6
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    Code:
         answer = n * factr (n-1);  //recursive call
         return (answer);
    Where what's hapenning.
    You calculate the answer and return it.

    Try this for some better insight
    Code:
    unsigned long factorial(unsigned long n){
        unsigned long result;
        printf("Calculating factorial of %u\n",n);
        result = n==0 ? 1 : n* factorial(n-1);
        printf("Returning factorial of %u which is %u\n",n,result);
        return result;
    }
    Last edited by xErath; 06-01-2005 at 11:08 PM.

  7. #7
    Registered User
    Join Date
    May 2005
    Posts
    207
    What I don't get is how it displays "Calculating factorial of n" when it starts at 20 & counts down & then it displays the answers counting forwards.

    Also, I don't get how it goes through the calculations first & then displays the answers after it's done. Especially using ONE variable that is changed with each calculation.

    mw

  8. #8
    Registered User
    Join Date
    May 2005
    Posts
    207
    Also, what does "results = n==0 ? 1" mean?

    mw

  9. #9
    Registered User
    Join Date
    May 2005
    Posts
    207
    Let me clarify my questions a bit:

    This is the output I'm getting:

    /*

    Type '0' to quit.

    Please specify a max range to calculate factorials.
    10
    Calculating factorial of 10
    Calculating factorial of 9
    Calculating factorial of 8
    Calculating factorial of 7
    Calculating factorial of 6
    Calculating factorial of 5
    Calculating factorial of 4
    Calculating factorial of 3
    Calculating factorial of 2
    Calculating factorial of 1

    2 2
    3 6
    4 24
    5 120
    6 720
    7 5040
    8 40320
    9 362880
    10 3628800
    */

    According to what I know about recursion/function calling, this is the output I SHOULD be getting:

    /*

    Type '0' to quit.

    Please specify a max range to calculate factorials.
    10
    Calculating factorial of 10
    10 3628800
    Calculating factorial of 9
    9 362880
    Calculating factorial of 8
    8 40320
    Calculating factorial of 7
    7 5040
    Calculating factorial of 6
    6 720
    Calculating factorial of 5
    5 120
    Calculating factorial of 4
    4 24
    Calculating factorial of 3
    3 6
    Calculating factorial of 2
    2 2
    */

    In order to calculate 10 different results I need 10 different variables, right?

    Not to mention how does it start from the largest number and calculate backwards if the larger result depends on the smaller results?

    Thanks!

    mw

  10. #10
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    Nop your wrong. Every code is executed sequentialy! so when you want 10!, you first need 9! for which you call the factr function again, but 9! also needs 8! which calls the function.

    Recursion is a function call made by the same function itself.
    Which compiler are you using. Debug your code and enter the factr function, keep steping into to see what hapenning
    Here's some examples
    Code:
    int pow10(int n){
        return n==0 ?1 : 10*pow10(n-1);
    }
    Code:
    int display_string(const char* s){//returns number of printed chars
        if(*s == 0 ) return 0;
        putchar(*s );
        return 1+string(s+1);
    }
    Code:
    void print_this_n_times(int n){
        if(n==0){
            printf("I'm inside the function but n is zero.... bye\n");
        }else{
            printf("I'm inside the function and I'm going to call myself because n is %d\n",n);
            print_this_n_times(n-1);
            printf(" function ended\n",n);
        }
    }
    Quote Originally Posted by Lionmane
    This is the output I'm getting:

    /*

    Type '0' to quit.

    Please specify a max range to calculate factorials.
    10
    Calculating factorial of 10
    Calculating factorial of 9
    Calculating factorial of 8
    Calculating factorial of 7
    Calculating factorial of 6
    Calculating factorial of 5
    Calculating factorial of 4
    Calculating factorial of 3
    Calculating factorial of 2
    Calculating factorial of 1

    2 2
    3 6
    4 24
    5 120
    6 720
    7 5040
    8 40320
    9 362880
    10 3628800
    */

    Not to mention how does it start from the largest number and calculate backwards if the larger result depends on the smaller results?
    Read your statement and look at the results.
    Last edited by xErath; 06-02-2005 at 07:27 PM.

  11. #11
    Registered User
    Join Date
    May 2005
    Posts
    207
    Ok, I think I get it now.

    There's more going on that what is immediately apparent.:

    The memory stack is used to store values temporarily. That's the piece I was missing. I thought that when the function was called, the variables were destroyed. That's not exactly correct though. Also: even though you're using only 1 variable in the function, the computer stores the different values for each function call seperately. That's how you're able to compute several different factorials using the same variable.

    I appreciate your help (and especially your patience)!

    mw

  12. #12
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    ah ! finally . yes that the point. each call is independant, yet controled.

    Quote Originally Posted by Lionmane
    Also, what does "results = n==0 ? 1" mean?
    http://www.cplusplus.com/doc/tutorial/tut1-3.html
    Conditional operator ( ? ).

    The conditional operator evaluates an expression and returns a different value according to the evaluated expression, depending on whether it is true or false. Its format is:
    condition ? result1 : result2
    if condition is true the expression will return result1, if not it will return result2.

    7==5 ? 4 : 3 returns 3 since 7 is not equal to 5.
    7==5+2 ? 4 : 3 returns 4 since 7 is equal to 5+2.
    5>3 ? a : b returns a, since 5 is greater than 3.
    a>b ? a : b returns the greater one, a or b.
    Last edited by xErath; 06-04-2005 at 12:06 AM.

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, 09: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, 10: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, 09: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, 02:29 PM