First time poster here, I hope that this question is acceptable.
As a small test I wrote an application that calculates the factorial of a number using both iteration and recursion. This seemed to work fine except when trying to calculate the factorial for numbers greater then 24.
For example, when calculating the factorial of 24 both methods give the correct answer of 62044840173323941.
When calculating the factorial of 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 discrepancy between the functions? I asked my colleagues and they also are unable to explain the behaviour.
#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 consideration.
The recursive version calculates 5 * (4 * (3 * (2 * 1)))
The iterative version calculates 1 * (2 * (3 * (4 * 5)))
The difference in the order of operations changes how the floating point arithmetic rounds, resulting in a different result.
The type double
is not an exact type. It promises to be an approximation of the correct value.
So both implementations are not guaranteed to be exact.
As your implementations are concerned there are two factors that could cause different answers.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With