Recursion inside For loop = program stuck

[trikolad]

I wrote a program to calculate a binom
the problem is that I have a recursion inside a for loop and
the program only works half way then get stuck.
If I take the recursive factorial function outside the for loop it works,
but of course I need it there to get the right answer.
I added a print for each cycle and verified that the output numbers until the program stops working are correct.

here it is:

#include <iostream>
#include <math.h>

using namespace std;

double myFactorial(double integer)
{
if( integer == 1)
     return 1;
else
       {
       return (integer * (myFactorial(integer-1)));
       }
}

int main()
{
    int i; double sum=0; double temp=0; int tot = 10; int n = 8;
    double fact; double fact1; double fact2;


 fact = myFactorial(tot);

    for(i=n; i<=tot; i++)
    {

     fact1 = myFactorial(i);
     fact2 = myFactorial(tot-i);

         temp=(fact/fact1/fact2)*pow(0.25,i)*pow((1-0.25),(tot-i));
sum+= temp;
cout << "temp =" << temp << endl;

    }

    cout << "binum =" << sum << endl;
    return 0;
}

I tried it both in codeblocks (installed software)where it gets stuck
and also on codepad.org where the output is:

1 temp =0.000386238
2 temp =2.86102e-05
3
4 Timeout

Suggestions?

[booradley60]

What happens when you call myFactorial and pass it a parameter that is less than one? Infinite recursion (at least, until you overflow the call stack and it crashes). Also, factorial is only a sensible operation for integers, so I would change the definition to look like this:

int myFactorial(int integer)
{
    //Perhaps you could handle this differently, but at least we're no
    //longer recursing infinitely.
    if( integer <= 1)
        return 1;
    else
    {
        return (integer * (myFactorial(integer-1)));
    }
}

[trikolad]

Thank you! works!!

now for knowledge,

I don't understand exactly why the recursion would try to go under 1 if 1 is the case to return.

I also don't understand how the function works as an int with these numbers
I tried bigger numbers - 132 and 78 instead of 10 and 8
and it worked only with double.

[booradley60]

 fact = myFactorial(tot);

    for(i=n; i<=tot; i++)
    {

     fact1 = myFactorial(i);
     fact2 = myFactorial(tot-i);
     //...
     }

The problem starts in the last pass through this loop. In that case, i and tot are equal. So guess what happens when you call myFactorial(tot-i); You're basically saying myFactorial(0), which, in your original code would cause recursion until your call stack overflowed.

As for your second question, the factorial sequence starts spitting out big numbers in a hurry. The result of factorial on a number like 132 is too big to be contained in an integer, but a double can hold it ( but with a certain degree of imprecision). Play with this program to see how quickly you run out of room to stick a factorial result in an integer.

#include <iostream>
#include <cmath>
#include <limits>

using namespace std;

int myFactorial(int integer)
{
    int runningTotal = 1;
    for(int i = integer; i > 1; i--)
    {
        runningTotal *= i;
        cout << "Running total is: " << runningTotal << endl;
    }
    return runningTotal;
}

int main()
{
    int input = 10;  //Change this value to something big and behold the weirdness
    cout << "The biggest number that an int can hold is: " << numeric_limits<int>::max() << endl;
    cout << "Calculating " << input <<"!" << endl;
    cout << "Press ENTER to go!" << endl;
    cin.ignore( numeric_limits<streamsize>::max(), '\n' );
    myFactorial(input);

    return 0;
}

[trikolad]

Very interesting!

I understand my problem with myFactorial(0)

Your example
1. What does this do: cin.ignore( numeric_limits<streamsize>::max(), '\n' );
and why do you need it here?

2. I don't understand why in your new example when I choose a bigger number it gives negative numbers from a specific cycle

This is the output for 20:

The biggest number that an int can hold is: 2147483647
Calculating 20!
Press ENTER to go!
Running total is: 20
Running total is: 380
Running total is: 6840
Running total is: 116280
Running total is: 1860480
Running total is: 27907200
Running total is: 390700800
Running total is: 784143104
Running total is: 819782656
Running total is: 427674624
Running total is: -18221056
Running total is: -163989504
Running total is: -1311916032
Running total is: -593477632
Running total is: 734101504
Running total is: -624459776
Running total is: 1797128192
Running total is: 1096417280
Running total is: -2102132736

[booradley60]

1. What does this do: cin.ignore( numeric_limits<streamsize>::max(), '\n' );
and why do you need it here?

I just put this here so that when you run the program, it pauses at this point. After I print out the prompt to press enter to continue, you can type as many characters as you want before you hit enter, and this line will say ignore all of those characters. It is a handy way to pause without worrying about someone dumping data into the input stream. I wanted to pause because that first bit of output about how big an integer can be could get blown away by the scrolling rows of factorial numbers.

2. I don't understand why in your new example when I choose a bigger number it gives negative numbers from a specific cycle

We are using signed integers. It is telling the program to treat your number as if it could be positive or negative. Due to the way in which computers handle signed numbers (http://en.wikipedia.org/wiki/Two%27s_complement), if our number gets too big it starts interpreting it like a negative number. Maybe it makes more sense to calculate factorial by starting at 1 instead of 'integer'. Take a look at this and you'll see that when the expected value goes beyond the reach of the maximum integer, values stop making sense.

#include <iostream>
#include <cmath>
#include <limits>

using namespace std;

int myFactorial(int integer)
{
    int runningTotal = 1;

    //I CHANGED THIS LOOP TO GO 1 TO INTEGER, INSTEAD OF INTEGER TO 1
    for(int i = 1; i <= integer; i++)
    {
        runningTotal *= i;
        cout << "Running total is: " << runningTotal << endl;
    }
    return runningTotal;
}

int main()
{
    int input = 10;  //Change this value to something big and behold the weirdness
    cout << "The biggest number that an int can hold is: " << numeric_limits<int>::max() << endl;
    cout << "Calculating " << input <<"!" << endl;
    cout << "Press ENTER to go!" << endl;
    cin.ignore( numeric_limits<streamsize>::max(), '\n' );
    myFactorial(input);

    return 0;
}

[trikolad]

Very interesting indeed!

Now, not only numbers become negative sometimes they are just wrong

The biggest number that an int can hold is: 2147483647
Calculating 20!
Press ENTER to go!
Running total is: 1
Running total is: 2
Running total is: 6
Running total is: 24
Running total is: 120
Running total is: 720
Running total is: 5040
Running total is: 40320
Running total is: 362880
Running total is: 3628800
Running total is: 39916800
Running total is: 479001600
Running total is: 1932053504
Running total is: 1278945280
Running total is: 2004310016
Running total is: 2004189184
Running total is: -288522240
Running total is: -898433024
Running total is: 109641728
Running total is: -2102132736


So if I want to get the correct numbers the right way to do it is double?

[booradley60]

double will make this problem emerge much further down the line, so you will be able to use bigger numbers. However, since we have a finite number of bits to represent our number, you will STILL eventually run into the overflow problem, given a large enough input.

If you do decide to use double, make sure you change all of the int types in factorial to double. That means return value, input parameter, for-loop counter, the works.

[trikolad]

Thank you very much!

This conversation has been very helpful!!