Recursion in Java Explained

stained-glass-recursion-featured-image — Image Credit - Pixabay

Recursion is considered to be a confusing area for many programming beginners. Reason for this confusion is because, most people, including me 😉 tried to imagine the mechanical process of a recursive problem step-by-step, which would often end up with confusion.

What the best, according to my opinion, is; just don’t try to imagine how computer works out the recursion. What we should have is a clear idea about the basic rules of recursion. Then, we would easily get an insight about the problem. We don’t bother to track how PC solves it. So, this article is written to give you a basic idea and rules about Recursion.

What is Recursion?

Let’s start with a simple example. Hope you are familiar with folders in a computer…

A folder (also called directory, or catalog) is a way to organize computer files. A folder is a storage space that many files can be placed into to group them together and organize the computer. A folder can also contain other folders.

Simple English Wikipedia

Now let’s focus our attention on the last two sentences. According to the definition, we can see, a folder may contain files or folders. Here’s the interesting part. A folder can itself contain sub-folders.

If a thing is defined in terms of itself or its type, recursion occurs.

Notice that, a sub-folder is a child of the parent folder. Though a sub-folder exhibits same properties of the parent folder, it’s just an instance of the containing folder. So, when you go deeper and deeper inside folders, the contents within a folder reduces and ultimately, we will reach to a folder that contains only files, but not folders.

If we want to list all the files in the folder, what can we do? Here’s the procedure in a pseudo code:

Print_files(directoryName){
    For all items in a directory{
        If directoryName contains only files{
        Print names of all files;
        Return;
        }
        Else if a directory contains a sub_directory{
            Print_files(sub_directory) 
        }
    }
}

Print_files(directoryName){

For all items in a directory{

If directoryName contains only files{

Print names of all files;

Return;

}

Else if a directory contains a sub_directory{

Print_files(sub_directory)

}

So, the definition of recursion:

If the solution to a problem is defined in terms of the same problem, but in a smaller scale, recursion occurs.

There are two important things to satisfy here.

The sub-problem should be inside the main problem (a subset of the main problem)

For example, we want to print all the files of My Documents folder in Local Disk (C:). Suppose we also have a shortcut to the hard disk partition New Volume (D:). If we consider the shortcut as a folder, the files of the partition are also get printed. But they are actually not a part of My Documents. Even they don’t belong to C: So, shortcut is not considered as a sub-folder, but a regular file.
There is an instance where the recursion method must return. This instance is called, the base-case.

That is, the problem cannot be subdivided further in to smaller forms of itself, beyond this point. The example is: when we reach a directory which has only files, the method Print_files() returns. So the base-case is a folder which has only files, but no sub-folders.

Infinite recursion

When two conditions don’t meet, there’s a potential to occur infinite recursion. Then our recursive method would never reach the base case. This is somewhat similar situation to the infinite loop. But, Java throws StackOverflowError in an infinite recursion. Otherwise, the process would take so much memory soon and the program will crash.

Code examples of Recursion

Greatest Common Divisor

Greatest Common Divisor(gcd) or Highest Common Factor is the largest positive integer that divides two or more non-zero integer values without a remainder.

For example 10 is the gcd of 20 and 50.

How do we mathematically find it? Remember secondary school math?
Use prime factorization;
20 = 2 x 2 x 5
50 = 2 x 5 x 5

so, 2 x 5 is common to both. That is, 10.

There’s another method to calculate the gcd. It is called as “Euclidean algorithm”. This is the method used in our recursion example. It is as follows,

Suppose we have 2 whole numbers X and Y. Also X > Y.

We divide X by Y. That is, X/Y

Now we can write the following equation by rearranging the terms;

X = q*Y + R

q is the quotient

and R is the remainder.

Eg:

252/105

252 = 2*105 + 42

Now here comes the theorem part;
According to the Euclidean algorithm, the gcd of X and Y is equals to the gcd of Y and R.

So, in our example, gcd of 252 and 105 equals to the gcd of 105 and 42.

105 = 2*42 + 21

Now we take 42 and 21 and gcd of these two numbers equals the gcd of our initial numbers, 252 and 105.

42 = 2*21 + 0

When the remainder is 0, the two numbers are divisible and hence one number is a factor of the other. The gcd of the two numbers is therefore, the smaller number. So, gcd is 21.

gcd(252,105) = 21.

As another example, we’ll take 20 and 50.

50 = 2 * 20 + 10

20 = 2 * 10 + 0

Therefore, gcd of 50 and 20 is, 10.

I have not given the proof of this Euclidean algorithm. If you are interested, you can check; Euclidean algorithm in wikipedia.
Now, how do we apply this knowledge to write a recursive algorithm?

public class GreatestCommonDivisor {
    /*this function will recursively calculate 
    *Greatest Common Divisor given that x>y
    *The value of GCD is returned as an integer
    */
    private static int calculateGcd(int x,int y){
        System.out.println(x+" "+y);
        if (y==0)
            return x;
        return (calculateGcd(y,x%y));
    }
 
    /*
    *This is the public method ensures the 
    *precondition of the private method calculateGcd() 
    *that is; y>x is satisfied. 
    *Then user is allowed to type x and y values 
    *without considering any preconditions.
    */
    public static int gcd(int x, int y){
        if (x<y){
            return calculateGcd(y,x);
        }
        return calculateGcd(x,y);
    }


    public static void main(String[] args){
        int gcd = gcd(252,105);
        System.out.println("gcd is: "+gcd);
    }
}

public class GreatestCommonDivisor {

/*this function will recursively calculate

*Greatest Common Divisor given that x>y

*The value of GCD is returned as an integer

private static int calculateGcd(int x,int y){

System.out.println(x+" "+y);

if (y==0)

return x;

return (calculateGcd(y,x%y));

}

*This is the public method ensures the

*precondition of the private method calculateGcd()

*that is; y>x is satisfied.

*Then user is allowed to type x and y values

*without considering any preconditions.

public static int gcd(int x, int y){

if (x<y){

return calculateGcd(y,x);

}

return calculateGcd(x,y);

}

public static void main(String[] args){

int gcd = gcd(252,105);

System.out.println("gcd is: "+gcd);

}

OUTPUT:

252 105

105 42

42 21

21 0

gcd is: 21

Now let’s quickly see the recursive feature. The method calculateGcd() is recursively called inside the same method with the statement

calculateGcd(y,x%y);

1	calculateGcd(y,x%y);

The base case is when y equals zero, return x. This is because, if it is zero, we cannot divide x by y because of division by zero error. So we just return the value of x.

If y is not zero, then the function has not reached the base case, so, the next set of statements are executed. That is, the recursion… But remember the second rule. The problem should now be smaller in size.

The numbers y and remainder R are now entered to the same calculateGcd() method to check their gcd. (x%y operation gives the remainder when x is divided by y)

Now, see, the size is smaller. When you call it recursively, ultimately, the problem will decompose to a remainder of zero at some point. You don’t have to bother about how it happens. Logic is clear. Problem is getting smaller and smaller. And we have a final base case of what to do and how to get the output when the problem reaches the smallest, undecomposable state. All clear… So, just let your PC to handle all the complexity of reaching the smallest state… 🙂 What we want is the final result. Not the intermediate process.

File Listing Example

Here’s another example of recursion. This is the actual Java code of previous directory listing pseudo-code.
The code uses the Class java.io.File to make File objects which store data about the actual folder/file they refer to. I have created a sample folder in Desktop having the directory structure as follows.

See the output of the following code. It lists all of these files and folders.

import java.io.*;
 import java.util.ArrayList;

public class Recursive_file_listing {
    public static void listFile(File directory){
        System.out.println("\nlisting files in directory: "+directory.getName());
        File[] fileList = directory.listFiles();
        int items = fileList.length-1;

        ArrayList<File> dirList = new ArrayList<File>();

        //first, the all items inside the directory is printed
        //and if the item is a sub-directory, it is saved in to
        //dirList
        for(int i=0; i<=items; i++){
            File item = fileList[i];
             System.out.println(item.getName());
            if (item.isDirectory())
               dirList.add(item);
        }

        //BASE CASE
        //if no sub-directories, there's nothing more to do
        //as the files names are already printed. So just return.
        if (dirList.isEmpty())
            return;

        //If there are sub-directories, recursively list the file names
        //inside each of them.
        for(File subDirectory: dirList){
            listFile(subDirectory); //RECURSION!!
        }
    }

    public static void main(String[] args){
        File file = new File("/home/User/Desktop/test_folder");
        listFile(file);
    }
 }

import java.io.*;

import java.util.ArrayList;

public class Recursive_file_listing {

public static void listFile(File directory){

System.out.println("\nlisting files in directory: "+directory.getName());

File[] fileList = directory.listFiles();

int items = fileList.length-1;

ArrayList<File> dirList = new ArrayList<File>();

//first, the all items inside the directory is printed

//and if the item is a sub-directory, it is saved in to

//dirList

for(int i=0; i<=items; i++){

File item = fileList[i];

System.out.println(item.getName());

if (item.isDirectory())

dirList.add(item);

}

//BASE CASE

//if no sub-directories, there's nothing more to do

//as the files names are already printed. So just return.

if (dirList.isEmpty())

return;

//If there are sub-directories, recursively list the file names

//inside each of them.

for(File subDirectory: dirList){

listFile(subDirectory); //RECURSION!!

}

public static void main(String[] args){

File file = new File("/home/User/Desktop/test_folder");

listFile(file);

}

OUTPUT:

listing files in directory: test_folder
folder2
folder1

listing files in directory: folder2
todo
6527905961_eabc9f4fcd_b.jpg
6527905507_9c9af4f917_b.jpg

listing files in directory: todo
document.tex
document.log
documentclass.pdf

listing files in directory: folder1
sampledoc2
doc1

This is the end of our recursion article. Hope you have understood it. Thanks for viewing 🙂 If you like it, please share it with your friends and that would be a lot of help to improve this site. In the next article, I’ll discuss about recursive linking, which is the beginning of data structures.