Java

Recursion in Java

Recursion in Java is the calling of a method, by the method, from within the method. This action repeats itself until a condition is met. The method should be a method in a class, other than one in the main class. The main class is the class that has the main() method. The name of the Java file is that of the main class. A static method in the main class can still be made recursive, but that will not be addressed in this article. This article explains recursion in Java, with three good examples.

Counting Integers from Zero

Consider a Java file with two classes: a private class as follows:

class AClass {
        void mthd (int no) {
System.out.print(no); System.out.print(' ');
            no = no + 1;
            if (no < 5)
mthd(no);
        }
    }

The method to be calling itself is, mthd(). It has the parameter “int no”. The method is in the class, AClass. This method counts from 0 to 4. The first line in the method has two statements. The first one prints the parameter, no. The second one prints a space on the right of this parameter printed. The next line adds 1 to no. The line that follows is an if-compound statement. It has the condition that has to be met. The condition to be met is when no reaches 5. If 5 has not been reached, “mthd(no);” calls itself with no that has 1 added to it.

The main class for this method can be,

public class TheClass {
        public static void main(String[] args) {
            int num = 0;
AClass obj = new AClass();
obj.mthd(num);
System.out.println();
        }
    }

The first statement in the main() method declares the integer, num assigning zero to it. For a method to be called, an object should be instantiated from its class. The next statement in the main() method instantiates an object, obj from AClass. The statement after uses this object to call the method, mthd(), passing to it the argument, num, which is 0. This is the start of the count. The last statement in the main() method prints a new line, after all the result has been printed. The output is:

0 1 2 3 4

The recursive method, mthd(), is called the first time from the main() method. After that it keeps calling itself, until a condition is met.

This kind of counting can be done for any range. To achieve it for any range, the start number of the range has to be assigned to num. Instead of 5 for the if-condition in the method, the number just after the range should be typed.

Adding a Range of Non-Continuous Given Numbers

Consider the numbers:

10, 20, 30, 40, 50, 60

The sum of the first 4 numbers is 100. That is: 10 + 20 = 30; 30 + 30 = 60; and 60 + 40 = 100. A recursive method can be adding these numbers to an increasing sum until the sum is less than or equal to 100. In order to add the first five numbers, the recursive method can be adding the numbers to an increasing sum until the sum is less than or equal to 150.

The strategy is to have all of these numbers in an array in the main() method. Then, pass the array as an argument to the recursive method. If the addition of the first four numbers is required, then when the sum reaches 100, the recursive method should stop calling itself. If the addition of the first five numbers is required, then when the sum reaches 150, the recursive method should stop calling itself. If the addition of the first six numbers is required, then when the sum reaches 210, the recursive method should stop calling itself.

The class for this recursive method can be:

    class AClass {
        int sum = 0, i = 0;
        void mthd (int[] arry) {
            sum = sum + arry[i];
i = i + 1;
            if (sum < 100)
mthd(arry);
        }
    }

This is for adding the first four numbers. The class has two fields, which are sum and i. i is for iterating through the array, beginning from index 0. The first statement in the recursive method, mthd(), adds the next number, to the sum, which is initially zero. The next statement increases i by 1, for the next array index of the next call. The statement after is the compound if-statement. The condition here is that the sum should not be above 100. So, for each call that the sum is not up to 100 (or above), the method is called again, passing the same array. In this situation, the condition is at the end of the method implementation.

The main() class for this can be:

public class TheClass {
        public static void main(String[] args) {
int[] arr = new int[]{10, 20, 30, 40, 50, 60};
AClass obj = new AClass();
obj.mthd(arr);
System.out.println(obj.sum);
        }
    }

The first statement in the main() method instantiates the array, with its elements. The second statement instantiates the object for AClass. The statement after, calls the recursive method, passing the array as argument. This is the first call of the recursive method. After that, the method will be calling itself until the required sum is reached. The last statement prints the final sum. The output for this case is 100.

Factorial

The factorial of 0, written as 0!, is 1. The factorials of 5, 4, 3, 2, 1 are as follows:

Factorial of 5 = 5 X 4 X 3 X 2 X 1 X 0! = 120

Factorial of 4 = 4 X 3 X 2 X 1 X 0! = 24

Factorial of 3 = 3 X 2 X 1 X 0! = 6

Factorial of 2 = 2 X 1 X 0! = 2

Factorial of 1 = 1 X 0! = 1

A program can be written so that when a number is sent to a recursive method, the recursive method will finally return the resulting factorial. Note that factorial can be calculated down to 1, instead of 0, and the result will still be the same.

The class for the recursive method can be:

    class AClass {
        int mthd (int no) {
          if (no == 1)      
            return 1;
          else      
return(no * mthd(no-1));    
        }
    }

The whole body of the method is a compound if-statement. If the number whose factorial is needed, is 1, what will be returned will be 1, as the factorial of 1 is 1. If the number is bigger than 1, then all the multiplication will have to be done, beginning from the number itself, going down by 1 unit.

The result is obtained when all the multiplication has been done. The return expression here is a method call. Its argument is the product of the number and the recursive method.

Assume that the number whose factorial is needed, is 5, then the argument of the first return call will be:

5 X mthd(4)

This expression will be reserved in memory, and the next call will be

5 X 4 X mthd(3)

This expression will be reserved in memory, and the next call will be

5 X 4 X 3 X mthd(2)

This expression will be reserved in memory, and the next call will be

5 X 4 X 3 X 2 X mthd(1)

Now, mthd(1) returns 1, due to the if-part statement, “if (no == 1) return 1;”, resulting in,

5 X 4 X 3 X 2 X 1 = 120

for the final return value.

The main class for this, can be:

public class TheClass {
        public static void main(String[] args) {
AClass obj = new AClass();
            int ret = obj.mthd(5);
System.out.println(ret);
        }
    }

With an argument of 5 for the first call, in the main() method, the final returned value is 120.

Conclusion

Recursion in Java is the calling of a method, by the method, from within the method. This action repeats itself until a condition is met.

About the author

Chrysanthus Forcha

Discoverer of mathematics Integration from First Principles and related series. Master’s Degree in Technical Education, specializing in Electronics and Computer Software. BSc Electronics. I also have knowledge and experience at the Master’s level in Computing and Telecommunications. Out of 20,000 writers, I was the 37th best writer at devarticles.com. I have been working in these fields for more than 10 years.