Factorial Using Recursion in Java

sums up the values of all factorials using recursion

The recursive sum method can behave exactly as your recursive factorial method. The only difference is that it uses addition instead of multiplication.

public static double sum(int numberinput) {
    if (numberinput == 0)
        return 1;
    else
        return factorial(numberinput) + sum(numberinput-1);
}

Finding the factorial using recursion with the BigInteger Class

There's an error in the code, you should put

  BigInteger factz = BigInteger.valueOf(a);

instead of BigInteger factz = BigInteger.ONE;

Recursive function to compute factorial fails after 20

This is what's known as "overflow". Longs are stored with 64 bits; their maximum value is 2^63 - 1 which is 9,223,372,036,854,775,807. Instead try using a BigInteger. Using BigInteger is a bit tricky as instantiation and operations are different than normal int/longs. Here's your code reworked for BigInteger:

public class BigIntFactorial {

    public static BigInteger factorial(BigInteger number) {
        if(number.equals(BigInteger.ONE)) {
            return BigInteger.valueOf(1);
        } else {
            return number.multiply(factorial(number.subtract(BigInteger.ONE)));
        }
    }

    public static void main(final String... arguments){
        for(Long number=1L;number<=30;number++){

            System.out.println("Factorial of " + number + "  : " + factorial(BigInteger.valueOf(number)));
        }
    }
}

output is:

Factorial of 1  : 1
Factorial of 2  : 2
Factorial of 3  : 6
Factorial of 4  : 24
Factorial of 5  : 120
Factorial of 6  : 720
Factorial of 7  : 5040
Factorial of 8  : 40320
Factorial of 9  : 362880
Factorial of 10  : 3628800
Factorial of 11  : 39916800
Factorial of 12  : 479001600
Factorial of 13  : 6227020800
Factorial of 14  : 87178291200
Factorial of 15  : 1307674368000
Factorial of 16  : 20922789888000
Factorial of 17  : 355687428096000
Factorial of 18  : 6402373705728000
Factorial of 19  : 121645100408832000
Factorial of 20  : 2432902008176640000
Factorial of 21  : 51090942171709440000
Factorial of 22  : 1124000727777607680000
Factorial of 23  : 25852016738884976640000
Factorial of 24  : 620448401733239439360000
Factorial of 25  : 15511210043330985984000000
Factorial of 26  : 403291461126605635584000000
Factorial of 27  : 10888869450418352160768000000
Factorial of 28  : 304888344611713860501504000000
Factorial of 29  : 8841761993739701954543616000000
Factorial of 30  : 265252859812191058636308480000000

Factorial using Recursion in Java

result is a local variable of the fact method. So each time the fact method is called, the result is stored in a different variable than the previous fact invocation.

So when fact is invoked with 3 as argument, you can imagine that its result is

 result3 = fact(2) * 3
 result3 = result2 * 3
 result3 = 1 * 2 * 3

Recursion in Java factorial program

first i want to explain some facts:

1. Factorial is computed by the following formula : n! = n * n-1 * n-2 * n-3 * .....* 3 * 2 * 1
2. Stack works in LIFO = last in first out or FILO = first in last out

so the code does the following it first puts all numbers from n to 1 in a stack then it pops each one and multiply it with the current result to get the factorial at the end

and by the way that is the iterative version for factorial (non-recursive), the recursive version will be like the following

int fact(int n)
{
    int result;

   if(n==1)
     return 1;

   result = fact(n-1) * n;
   return result;
}

Explain recursion in factorial method

The machine does not know what factorial is, the code there tells it how to calculate a factorial. It does this by saying "Is the number you gave me 1?" and until it is, returns the number times the function return of n - 1, essentially this will cascade into the calculation of a factorial.

This is easily seen if you take an example:

3! = 3*2*1

Or

3! = 3*2!

Which is what the return method gives in the form:

factorial(n) = n * factorial(n-1)

The program given:

factorial(3);

Will go through the following:

1. Is 3 equal to 1?
2. It is not so it returns 3*factorial(2)
3. In order to obtain 3*factorial(2), it calculates factorial(2).
4. Now it checks: is 2 equal to 1?
5. It is not so it returns 2*factorial(1), since it is returning to the step three, that overall return will now be 3*2*factorial(1).
6. Next the program checks: is 1 equal to 1?
7. It is so it returns 1.
8. This is returned to our call in step five: 2*factorial(1) becomes 2*1 = 2, which returns to the call from step 3, our first call, giving us 3*2 = 6, which is what the function will return overall.

This method could do with some tweaking though. Imagine you supplied it with 0? It would continuously call the factorial method on an infinite recursion because the sequence 0,-1,-2,-3,-4,... will never reach 1. A better method could look like this:

private static long factorial(int n) {

    if (n == 1 || n == 0) {
        return 1;
    } else if (n < 0) {  // factorials are not defined below 0, they can be interpolated
        return null;     // though, see note below
    } else {
        return n * factorial(n - 1);
    }
}

This function will now cover factorials for the whole range of integers, using a null solution for negative numbers. The definition for a factorial of n is defined as the product of the integers between 1 and n; see this. Factorials of negative integers, floating point numbers, and complex values are also defined or can be interpolated as noted in the link in the previous sentance, but these are much more complex than a simple recursive factorial.

Java recursive method to find factorial returns negative output

I know this is marked duplicate, but solving it using recursion and BigInteger just coz you (@Abdalnassir Ghzawi) requested for it.

public BigInteger factorial(BigInteger n) {
    BigInteger res;
    if (n == BigInteger.ZERO) {
        res = BigInteger.ONE;
    } else {
        res = n.multiply(factorial(n.subtract(BigInteger.ONE)));
    }

    return res;
}

You'll need to call it using :

System.out.println(new RecursiveFunctionsExamples().factorial(new BigInteger("6")));

Hope it helps!

Recursive function for finding factorial of a number

Your program suffers from undefined behavior.

In the first call to factorial(5), where you have

return number * factorial(--number);

you imagine that this is going to compute

       5      * factorial(4);

But that's not guaranteed!

What if the compiler looks at it in a different order?

What it if works on the right-hand side first?

What if it first does the equivalent of:

temporary_result = factorial(--number);

and then does the multiplication:

return number * temporary_result;

If the compiler does it in that order, then temporary_result will be factorial(4), and it'll return 4 times that, which won't be 5!. Basically, if the compiler does it in that order -- and it might! -- then number gets decremented "too soon".

You might not have imagined that the compiler could do things this way.

You might have imagined that the expression would always be "parsed left to right".

But those imaginations are not correct.

(See also this answer for more discussion on order of evaluation.)

I said that the expression causes "undefined behavior", and this expression is a classic example. What makes this expression undefined is that there's a little too much going on inside it.

The problem with the expression

return number * factorial(--number);

is that the variable number is having its value used within it, and that same variable number is also being modified within it. And this pattern is, basically, poison.

Let's label the two spots where number appears, so that we can talk about them very clearly:

return number * factorial(--number);
       /* A */             /* B */

At spot A we take the value of the variable number.

At spot B we modify the value of the variable number.

But the question is, at spot A, do we get the "old" or the "new" value of number?

Do we get it before or after spot B has modified it?

And the answer, as I already said, is: we don't know. There is no rule in C to tell us.

Again, you might have thought there was a rule about left-to-right evaluation, but there isn't. Because there's no rule that says how an expression like this should be parsed, a compiler can do anything it wants. It can parse it the "right" way, or the "wrong" way, or it can do something even more bizarre and unexpected. (And, really, there's no "right" or "wrong" way to parse an undefined expression like this in the first place.)

The solution to this problem is: Don't do that!

Don't write expressions where one variable (like number) is both used and modified.

In this case, as you've already discovered, there's a simple fix:

return number * factorial(number - 1);

Now, we're not actually trying to modify the value of the variable number (as the expression --number did), we're just subtracting 1 from it before passing the smaller value off to the recursive call.
So now, we're not breaking the rule, we're not using and modifying number in the same expression.
We're just using its value twice, and that's fine.

For more (much more!) on the subject of undefined behavior in expressions like these, see Why are these constructs using pre and post-increment undefined behavior?

---

Related Topics