A method which calls itself is called recursive method. Recursive methods are very useful when we want to process data stored in list structure or in tree structure. Some types of functionality can not be implemented without recursive method. e.g., printing the family tree.
Every recursive method calls itself in the body of its method. Also every recursive method will have a condition where it does not call itself. With out this condition, the method will go into infinite loop causing
StackOverflowError .
Factorial Using Recursion CODE class FactorialUsingRecursion OUTPUT Factorial of 5 is 120 DESCRIPTION The method factorial defined here is a recursive method. As we can see at LINE B, it is calling itself. It also has a condition in LINE A. When this condition is true, it will not call itself, hence stopping the recursive calls.
factorial(n) = 1 * 2 * 3 * .... * n-1 * n
This can be rewritten as
factorial(n) = n * factorial(n-1); factorial(n-1) = (n - 1) * factorial(n-2); ... ... factorial(3) = 3 * factorial(2); factorial(2) = 2 * factorial(1); factorial(1) = 1; and for 4 : factorial(4) = 4 * factorial(3) and for 3 : factorial(3) = 3 * factorial(2) and for 2 : factorial(2) = 2 * factorial(1). Since we have the given the factorial(1) as 1 in LINE A , it will not call the method again and simply returns 1 .
Since the recursion stops when the i value is 1, the factorials will be calculated, as shown below.
factorial(1) = 1; factorial(2) = 2 * factorial(1) = 2 * 1 = 2; factorial(3) = 3 * factorial(2) = 3 * 2 = 6; factorial(4) = 4 * factorial(3) = 4 * 6 = 24; factorial(5) = 5 * factorial(4) = 5 * 24 = 120;
|