Explain recursion in factorial method

Question

I am new to computer science and learning recursion methods. Can someone explain this method briefly?

 import java.util.Scanner;

public class factorial {

    public static void main(String args[]) {

        Scanner scan = new Scanner(System.in);

        int n = scan.nextInt();

        System.out.print(factorial(n));

    }

    private static long factorial(int n) {      // HERE I DON'T UNDERSTAND HOW 
                                               //  THE MACHINE NOWS WHAT IS "factorial"
        if (n == 1)
            return 1;
        else
            return n * factorial(n - 1);               // ??
    }

}

Answer 1

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.