Admin

The basics of recursion and how it works. Including 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, then putting these results together to achieve the original intent.

For this example, a factorial (say 6!), can be written as:
[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]

which can again be written as:
5*4!


...
and this pattern continues until we have:
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, and 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. for this time. Recursion on larger sets can be more efficient. There are cases where loops should be used. Perhaps i'll discuss that another day.

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!
recursivly
result = n*(n-1)! as described above
*With this we can design a recursive method which calculates a factorial.

Do keep i mind, 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 0 and including 2 as they are equal to themselves, and 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! 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 recrusion does and is, it should be easier to determine the base cases, then look for similarly simple cases and the connection between them.