CODEWITHSUNDEEP
c++recursion
imtk
imtk

Reputation: 1548

What is wrong with this recursive factorial implementation?

I compiled and run in my computer, and it executes correctly. I tried IDEONE, and I got a successful answer.

But when I submit it in SPOJ, I'm getting a wrong answer. Is something wrong in this implementation?

#include <iostream>
#include <cstdio>

using namespace std;

int factorial(int n) {
    if (n <= 1)
        return 1;

    return n * factorial(n - 1);
}

int main() {
    int t;
    int n;

    cout << "";
    cin >> t;

    for (int i = 0; i < t; i++) {
        cout << "";
        cin >> n;

        printf("%d\n", factorial(n));
    }

    return 0;
}

Upvotes: 2

Views: 192

Answers (1)

CLL
CLL

Reputation: 331

The problem with the above code is due to the finite space we can use to store the value of an int. On a 32-bit machine, int's have 32 bits (value 0 or 1), which means that the maximum value an unsigned int can have is (2^31 - 1) and the maximum value an int can have is (2^30 - 1) (since it needs one bit to denote whether it is positive or negative, while the unsigned int is always positive and can devote that bit to just regular value).

Now, that aside, you should look into ways of storing the value of a very large number in a different data structure! Maybe an array would be a good choice...

Just to brainstorm, imagine creating an int bigInteger[100] (that should be large enough to hold 100!). To multiply two of your numbers, you could then implement a bitMultiplication(int bitNum[], int num) function that would take in your array by reference and perform bitwise multiplication (see the following post for details: Multiplying using Bitwise Operators).

Use that bitMulitiplication(int bitNum[], int num) instead of the regular multiplication in your recursive factorial function, and you should have a function that works on large n!

Upvotes: 1

Related Questions