Different answers when calculating factorial using iteration and recursion

The first poster is here, I hope this question is acceptable.

As a small test, I wrote an application that calculates the factorial of a number using iteration and recursion. This seemed to work just fine, except when trying to calculate the quotient for numbers greater than 24.

For example, when calculating factorial 24, both methods give the correct answer 62044840173323941.

When calculating factorial 25, however, the answers differ. The recursive method gives the answer as 1.5511210043330986e + 025, while the iterative method gives the answer as 1.5511210043330984e + 025.

According to Wolfram Alpha, the correct answer should be the same as the iterative method, so why the divergence between functions? I asked my colleagues, and they also cannot explain the behavior.

#define TEST_CASE 25

double GetFactorialRecursive(double i)
{   
    if (i == 1)
    return i;
    else
    return i * GetFactorialRecursive(i - 1);
}

double GetFactorialIterative(double i)
{
    double result = 1.0;
    for (; i > 0; --i)
        result *= i;
    return result;
}

int main ()
{
double recres = 0, itrres = 0; 
recres = GetFactorialRecursive(TEST_CASE);
itrres = GetFactorialIterative(TEST_CASE);

if (recres != itrres)
    std::cout << "Error" << "\n";
std::cout << std::setprecision(25) << "Recursion: " << recres << ", Iteration: " << itrres << "\n";
return 0;

}

Thank you for your attention.

+5
source share
3 answers

The recursive version computes 5 * (4 * (3 * (2 * 1)))

The iterative version computes 1 * (2 * (3 * (4 * 5)))

The difference in the order of operations changes as arithmetic floating point rounds, which leads to a different result.

+9
source

Type is double not an exact type . He promises is an approximation to the correct value.

Therefore, both implementations are not guaranteed.

, .

  • .
  • . Intel- (x86 x86-64) 80 , .
+4

The order of multiplications is different, giving different results due to rounding with floating point.

If you change the loop forto go from 1to i(and not from ito 1), you should get the same result as in the recursive version.

+2
source

All Articles