Converting a Java Method into a recursive method? (insertion sort)

Question

I'm trying to understand recursion and how to turn my currently iterative insertion sort into a recursive one.

What would I need to do to my code to make it recursive?

• I think I need a base case so it doesn't become an infinite loop.
• I'm not sure I entirely understand recursion. Maybe you can make it clearer for me?
• I've done a lot of reading but I still don't know where to start.

Here is my code:

public class InsertionSort
{

    public static void main(String a[])
    {

        int i;
        int array[] =
        { 8, 33, 12, 99, 0, 17 };

        System.out.println("Values of Array before the sort: ");

        for (i = 0; i < array.length; i++)
        {
            System.out.print(array[i] + "  ");
        }

        insertion_srt(array, array.length);

        System.out.println("");
        System.out.println("Values of Array after the sort: ");

        for (i = 0; i < array.length; i++)
        {
            System.out.print(array[i] + "  ");
        }

    }

    public static void insertion_srt(int array[], int n)
    {

        for (int i = 1; i < n; i++)
        {

            int j = i;
            int B = array[i];

            while ((j > 0) && (array[j - 1] > B))
            {
                array[j] = array[j - 1];
                j--;
            }

            array[j] = B;
        }
    }
}

Answer 1

Transforming the outer for loop is kind of trivial. To overcome the while loop you need a little recursive helper function. You have to call the function in your main as insertion_srt(array, 0, array.length):

public static void insertion_srt(int array[], int beg_index, int n) {
    if(beg_index >= n-1)
            return;
    int i = beg_index + 1;
    int j = i;
    int B = array[i];
    j=helper(array, j, B);
    array[j] = B;
    insertion_srt(array, beg_index + 1, n);
}

private static int helper(int[] array, int j, int B) {
    if(j <= 0 || array[j-1] <= B)
        return j;
    array[j] = array[j - 1];
    return helper(array, j-1, B);
}

Answer 2

This is great approach I personally likes. It does use three methods but they're very simple to understand. Think of the insertionOut as the outer for loop and the insertionIn as the inner nested for loop

public static void insertionRecursive(int[] a){
    if(a.length > 0){ // base case
        insertionOut(a, 1, a.length);
    }
}   
private static void insertionOut(int[] a, int i, int length){ //outer loop
    if(i < length){ // iterates from 1 to the length
        int temp = a[i]; // temp value
        int k = i;
        insertionIn(a, k, temp);
        insertionOut(a, i + 1, length); // iterates through the loop
    }
}
private static void insertionIn(int[] a, int k, int temp){ // inner loop
    if(k > 0 && a[k - 1] > temp){
       //this does a basic swap
        a[k] = temp;
        a[k] = a[k - 1];
        a[k - 1] = temp;
        insertionIn(a, k - 1, temp);    // iterates through the loop
    }
}

Answer 3

A good way to understand how recursion works is to understand the concept of Divide and conquer algorithm. This technique is a basis of efficient algorithms for all kinds of problems.

The idea behind it is to divide a problem into smaller subproblems that can all be solved in the same way:

• Divide into 2 (or more) subproblems.
• Solve each subproblem recursively.
• Combine the results.

Insertion sort is not the best example of a divide and conquer algorithm, but it can still be approached this way. You can divide the problem into 2 subproblems:

• last element
• everything else

This way you will obtain so called tail recursion. All loops are relatively easy to transform into tail recursions.

public static void insertion_srt(int array[], int n, int j) {
    if (j < n) {
        int i;
        int temp = array[j];

        for (i=j; i > 0 && array[i-1] > temp; i--) array[i] = array[i-1];
        array[i] = temp;

        insertion_srt(array,n, j+1);
    }
}

Answer 4

Try this simple recursive approach:

public static void insertionSort(int[] array, int index) {
    if(array.length == index + 1) return;

    insertionSort(array, index + 1);

    // insert array[index] into the array

}