Recursive In Java

Methods - Importance >
Siva Nookala - 12 Apr 2016

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

Try it Online

class FactorialUsingRecursion
{
    public static void main(String s[])
    {
        System.out.println("Factorial of 5 is " + factorial(5) );
    }
    
    public static int factorial(int i)
    {
        if( i == 1 )    // LINE A
        {
            return 1;
        }
    
        return i * factorial(i - 1); // LINE B
    }
}

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.
As we know the factorial of any number is the product of all the numbers before it. We know factorial of n is

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;

Using this principle, for calculating the factorial of 5 : factorial(5) = 5 * factorial(4)
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;

Try it Online

A famous proverb to explain the importance of recursive methods is To Iterate is Human, to Recurse, Divine.

Java Program To Find Simple Interest Using Methods

Java Array