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;
        }
    }
}

Mind, that though recursive solutions are often more elegant than interative ones, java is not a well suited language for recursion since it does no tail call optimization. That is a compiler's ability to convert a recursive function into an iterative form and thus preventing the call stack from being blown. So in java having an arbitrary depth of recursions will eventually lead to out-of-memory exceptions. — nansen, Oct 03 '12 at 09:58
Have you read this [explanation of recursion](http://stackoverflow.com/questions/717725/understanding-recursion) and understood everything? — phant0m, Oct 03 '12 at 11:43

score 1 · Answer 1 · answered Dec 10 '14 at 10:24

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
    }
}

user1581900 · Answer 2 · 2012-10-03T10:19:12.740

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);
    }
}

I suggest you add more information to your answer. As of now, it's not exceedingly helpful, but it's a good start. — phant0m, Oct 03 '12 at 09:54

halex · Accepted Answer · 2012-10-03T10:10:13.517

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);
}

score -1 · Answer 4 · answered Oct 03 '12 at 09:49

-1

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

}

answered Oct 03 '12 at 09:49

Anshu

7,783
5
31
41

How would i implement this with my code above? Maybe its too simple i'm just not understanding it :/ – binary101 Oct 03 '12 at 10:28

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

4 Answers4