recursive c++ factorial giving negative values for multiple entries

Question

I am kind of new to C++ and I am trying to write a recursive factorial calculator. I did write but it is giving multiple negative values for entries like 20, 21, 22, 33, 40, etc. And also the code fails to calculate factorial for integers greater than 65 despite my attempt to enable using long long int. Can someone please explain to me why this is happening? I didn't have any issue in python. Why is it happening in c++?

Here is my code:

#include "stdafx.h"
#include <iostream>
#include <conio.h>

using namespace std;

 long long int factorial(long int n) {
    long long int temp;
    if (n == 1 || n == 0) {
        return 1;
    }

    else {
        temp = n*factorial(n - 1);
        return temp;
    }
}

int main()
{
    int n, i;
    cout << "Enter positive integer or zero: ";
    cin >> n;

    while (n < 0 || cin.fail()) {
        cout << "\nFactorial cannot be calculated for n is negative." << endl;
        cin.clear();
        cin.ignore(numeric_limits<streamsize>::max(), '\n');

        cout << "Please try with integer >= 0: ";
        cin >> n;
    }

    cout << factorial(n) << endl;

    _getch();

    return 0;
}

Answer 1

It's simple overflow issue. You already know the result from python, so you can check if it's too big for the type you're using (obviously it is).

As for python, it has built-in support: Handling very large numbers in Python

Use a C++ bigint library.

Answer 2

What you are experiencing is undefined behavior as a result of integer overflow. you are using a long long int which is a signed integer most likely to be represented as an 8 byte integer (this is platform specific).

Assuming from here one that your long long int is only 8 bytes(64 bits) that would mean that the maximum positive value that it can store is approximately 2^63 which is approx 9.223372037e+18.

Trying to calculate the factorial of numbers like 20, 21, 22, 33, 40, etc will result in a value larger than the maximum that a long long int can store which will result in undefined behavior which in this case is manifesting as integer wraparound.

To fix this you would need to use an integer data type capabale of representing larger values. I would start by switching to an unsigned long long int which will get you twice the range if numbers because an unsigned type deals only in positive numbers. That is just a band-aid on the issue though. To truly handle the problem you will need to find a library that does arbitrary precision integer math. (A bigint library)

(There are also some platform specific things you can do to ask your compiler for a 128bit int, but the better solution is to switch to a bigint data type)

EDIT:

I should clarify that by "bigint" i was not necessarily referring to any particular library. As suggested in the comments there are multiple options as to which library could be used to get the job done.