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

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

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

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.

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;

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

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;
}

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

Also, what does "results = n==0 ? 1" mean?

mw

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

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);
    }
}

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.

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

ah ! finally . yes that the point. each call is independant, yet controled.

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.