Java recursion. Binary search and reversing arrays

Introduction

• This series is going to be dedicated to learning and understanding data structures and algorithms in Java. All the information I am using is coming from the book, Data Structures and Algorithms in Java by Michael T. Goodrich and Roberto Tamassia and the California State Polytechnic University course, which is free and can be found HERE, shout out professor Tang. Please do not buy the book it is expensive and can be found online for MUCH cheaper.

What is Recursion?

• One way to describe repetition within a computer program is the use of loops, like the for loop and while loop. However, an entirely different way to achieve repetition is through a process known as recursion. Recursion is a technique by which a method makes one or more calls to itself during execution. Recursion is a very fundamental topic inside of computer science as many algorithms and data structures use it to simplify the looping process.

Method calls

• Recursion is essentially just repeated method calls. So we have to ask ourselves. Where are these calls being stored and what happens when they are finished? In Java, each time a method is called (recursive or otherwise) an activation record(also called activation frame or just frame) gets created. This frame stores information about process of the invocation of the method. The frame stores, method parameters, local variables and information about which line the method is currently executing. Each one of these frames is then stored on the activation stack(the JVM creates on startup), which is a list of all functions representing the state of our program. Once a method invocation finishes the frame associated with that function is removed from the activation stack and the program no longer holds any memory of it.

Constructing recursive algorithms

• When creating an algorithm that uses recursion, we need to consider two basic principles:

1) Test for base case : Every recursive algorithm we create should begin by testing for a set of base cases(there should be at least 1). The base cases should be defined so that every possible chain of recursive calls will eventually reach a base case.

2) Recursion : If the base case is not met, we should perform more recursive calls. Each recursive call should be defined so the call progresses towards the base case.

The BinarySearch algorithm

• Before we go any farther it is very important to understand that a binary search algorithm is meant to be run on a sorted sequence of elements. So only use this algorithm if you have a sorted sequence at your disposal .Ok, so enough talk lets look at some code. Ultimately this is what the binarySearch algorithm looks like:

public boolean binarySearch(int[] data, int target, int low, int high){
        if(low > high){
            return false;
        }
        else{
            int mid = (low + high) / 2;
            if(data[mid] == target){
                return true;
            }
            else if(target < data[mid]){
                return binarySearch(data,target,low,mid -1);

            }
            else{
                return binarySearch(data,target,mid +1,high);
            }
        }
    }

• The equation might look rather complex but its not, so lets break things down line by line. There are 4 main sections of this algorithm that we should take a look at:

1) the parameters : as we can see the method takes in 4 parameters, data is the sorted array we are searching, target is the integer we are searching for, low is the starting of our array, high is the end of our array.

2) Base cases : as I stated earlier, in recursion a base case is fundamental. For this algorithm the first base case is:

if(low > high){
            return false;
        }

• This base case works perfectly because as we make recursive calls the low parameter will grow and or the high parameter will shrink. It will only be triggered if we have not found our desired target item.

• The other base case will get called if we do find our desired target:
  

if(data[mid] == target){
                return true;
            }

• once either of our base cases get triggered, there will be no more recursive calls

3) The mid variable : The mid variable is very important because it holds the value that will be used to find the mid point for our algorithm: int mid = (low + high) / 2;. It is what gives our algorithm its efficiency

4) Recursive calls : can't have a reclusive algorithm without some recursive method calls:

else if(target < data[mid]){
                return binarySearch(data,target,low,mid -1);

            }
            else{
                return binarySearch(data,target,mid +1,high);
            }

• The important thing to notice with the two above blocks is the placement of the mid variable. The placement is what allows us to quite literally not care about anything beyond the mid parameter.

Performance of the Binary Search algorithm.

• Now if we had to do a traditional loop of a sequence of sorted items and check each individual item that would run in O(N) time. However, since we are able to remove whole chucks of the list thanks to the mid parameter equation, the runtime of our algorithm is O(logN).

Reversing a array with recursion

• The code for this one is pretty straight forward but it definitely warrants an explanation:

public void reverseArray(int[] data,int low,int high){
        if(low < high){
            int temp = data[low];
            data[low] = data[high];
            data[high] = temp;
            reverseArray(data, low + 1, high -1);
        }
    }

• again, lets look at the parameters first, data will represent our starting array, low will be the front of the array, high will be the end of the array. As we make more recursive calls the parameters will be altered slightly to work towards the base case. Despite not looking like it has a base case, the base case is when low > high at that point the method will stop making recursive calls.
• I believe that the code above is easy enough where you can reason what is going on. However, there is the question of why do we need the temp variables ?. Can't we do something like this:

data[low] = data[high];
data[high] = data[low];

• Obviously some of you see the problem right away. However, if you were like me and thought it should work, run this code and see the weird repetitive output it gives:

if(low < high){
            data[low] = data[high];
            data[high] = data[low];
            reverseArray(data, low + 1, high -1);
        }

• So the reason that we need a temp variable is to hold the original value of data[low]. because the section data[low] = data[high]; actually overwrites the original value.

Conclusion

• Thank you for taking the time out of your day to read this blog post of mine. If you have any questions or concerns please comment below or reach out to me on Twitter.