The basics of recursion and how it works are covered in this tutorial. It also includes a factorial example.
You probably use recursion often, whether you realize it or not. It is a process of subdividing a problem into several smaller problems with easily calculated results and then putting these results together to achieve the original intent.
For this example, a factorial (6), can be written as follows:
[6*5*4*3*2*1]
We can sub-divide this into:
6*5!
Now, we have a smaller problem of similar type to solve:
[5*4*3*2*1]
This can again be written as follows:
5*4!
…
This pattern continues until we have the following:
2*1! (In the code example, we stop at 2! since 2! = 2.)
We can implement this recursion such that any value can be given such that n! can be calculated recursively.
*Yes, this particular example can be done with a for loop. For small values, a for loop would be more efficient, but have you ever run a for loop that looped 10,000 or more times? It takes forever, and your computer basically stops responding. Recursion on larger sets can be more efficient. There are cases where loops should be used, but this is a topic for another tutorial.
For Loop CODE:
public static int factorial(int num) {
if(num < 2)
return num;
int result = 1;
for (int i=2; i<=num; i++)
result *= i;
return result;
}
*Note that this example does not handle negative values. In such a case, the given value would be returned.
To define the recursive definition, we need to know what the problem is:
result = n!
recursively
result = n*(n-1)! as described above
*With this, we can design a recursive method which calculates a factorial.
Do keep in mind that recursion is a self-repeating method, so we need to write all base cases to stop the recursion when the smallest case has been reached and start returning values for the answer.
Recursive CODE:
public static int factorial(int num) {
//BASE CASES: 0! = 1 and factorial not defined for negative ints
if (num < 0) return -1;
if (num == 0) return 1;
if (num <= 2) return num;
//RECURSIVE STEP: n! = n * (n-1)!
return (num * factorial(num - 1));
}
This example returns -1 for all negative factorials and returns the given value for factorials between zero and including two as they are equal to themselves. It returns 1 for the special case of 0!
For our example of 6!, num is 6, and thus tries to return 6*5!, but java will have to evaluate 5! first, calling this same method with num = 5 before it can return this value.
Thus each call repeats this same effect until 2 is reached and 2 is returned.
Using numbers 6! as an example in order of calls and recursive answer:
return (6 * factorial(5));
return (5 * factorial(4));
return (4 * factorial(3));
return (3 * factorial(2));
return 2;
*We reached a bas case and now the recursion fills in the call values factorial(n-1) in the reverse order they were called:
return 2;
return 3*2;
return 4*6;
return 5*24;
return 6*120;
*which returns 720 = 6!
Not all recusive definitions are this easy to spot, but with a better understanding of how and what recursion does and is, it should be easier to determine the base cases. Then you can look for similarly simple cases and the connection between them.
Questions/Comments: [email protected]
-William. § (marvin_gohan)
