Learning Java recursion from book, Java, a complete reference

Question

Learning about recursion and having trouble with the code posted below, in line 6,

int result=fact(n-1)*n;

When I delete "fact" the program acts like I think it would, printing out:

Factor of 3 6
Factor of 4 12
Factor of 5 20

but with the "fact" in it gives the output below? What is this line doing, and what is "fact" ? thanks everyone.

Factor of 3 6
Factor of 4 24
Factor of 5 120

Answer 1

Factorial is often used as an example of something which can be performed using recursion.

For example, factorial of 5 is calculated as follows:

5! = 5 * 4 * 3 * 2 * 1

Also, there is another way of thinking about it:

5! = 5 * 4!
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1

The way the second series of equalities are written, it can be seen that a factorial can be calculated in a recursive fashion. For example:

5! = 5 * 4! --> 5! = 5 * (4 * 3!) --> 5! = 5 * (4 * (3 * 2!)) --> and so on.

The fact function in the question is performing the factorial function as written in the second series of equalities:

fact(n) = n * fact(n-1);

So, when the fact method is being called, way it is being called can be thought as something like the following:

fact(5) --> fact(5 * fact(4)) --> fact(5 * fact(4 * fact(3))) --> and so on.

Also, it should be noted as Kip points out in the comments, calculating the factorial of a number can be much easily and quickly calculated by iterating over the range of numbers from n to 1 and multiplying it together to calculate the result.

Answer 2

Apparently this is the classic example of recursion using the factorial calculation.

What you're calling fact(N) is usually denoted by N! (by mathematicians, anyway)

n! = n x (n-1) x (n-2) ...

so 5! = 5 x 4 x 2 x 1 = 120
4! = 4 x 3 x 2 x 1 = 24

Incidentally, this may be a little counterintuitive, but 0! is defined as 1

Answer 3

When you remove the call to fact again you are just doing:

println(n * (n-1))

You may want to try doing a factorial with just a loop and see how different the code is.

Recursion can be useful, but, you will be limited in how large of (n) you can call, as you will eventually overflow the stack, since the calculations won't happen until you reach the condition that marks the end of the recursion.

To better understand recursion you can look at this link: http://en.wikipedia.org/wiki/Recursion_(computer_science)