How do I make a sort method using recursion?

Question

I'm learning recursion and I was instructed to make a recursive method that sorts an array. So far I have this:

public static void sort(int [] a, int i) {
    if(i == a.length - 1){
        System.out.println(a[i]);
    }
    if(i < a.length) {
        if(a[i] > a[i+1]) {
            int temp = a[i+1];
            a[i+1] = a[i];
            a[i] = temp;
            sort(a,i++);
        }
        printArray(a); 
    }
}

Now I know this is wrong because I still really don't quite understand how to use recursion in my programming. If someone could just help me with the method I would appreciate it, but and explanation on how to use recursion in my programming would be great. Thank you in advance.

Answer 1

From Wikipedia:

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration). The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.

Recursion is a great tool to know how to use in programming. It's main idea is to break down a large hard to process idea or action into smaller more digestible ideas or actions. While sorting is a good example of recursion, I'd like to present to you my favorite example of recursion, recursive string matching.

If you have a key you're matching your string to which includes wild cards, recursion is a good way to break up the potential matches into a easier to match problem.

If we have a key of a*b?c (where * can represent any number of characters and ? is any single character) and we want to check azyxbwc to see if they fit the key the process is pretty simple once you get the hang of it (I'll be writing a rough psuedo-code for the example).

Enter Function with key='a*b?c' and input='azyxbwc'
Retrieve first letter of key --> 'a'
Retrieve first letter of input --> 'a'
Does 'a' == 'a'  --> true
If true, call function with remaining key & input

Enter Function with key='*b?c' and input='zyxbwc'
Retrieve first letter of key --> '*'
Retrieve second letter of key --> 'b' //if first is a wildcard, get a second
Retrieve first letter of input --> 'z'
Does '*' == 'z'  --> false
Does 'b' == 'z'  --> false
Is '*' a wildcard --> true
If true, call function with remaining key & input //key keeps wild b/c second letter didn't match

Enter Function with key='*b?c' and input='yxbwc'
Retrieve first letter of key --> '*'
Retrieve second letter of key --> 'b' //if first is a wildcard, get a second
Retrieve first letter of input --> 'y'
Does '*' == 'y'  --> false
Does 'b' == 'y'  --> false
Is '*' a wildcard --> true
If true, call function with remaining key & input

Enter Function with key='*b?c' and input='xbwc'
Retrieve first letter of key --> '*'
Retrieve second letter of key --> 'b' //if first is a wildcard, get a second
Retrieve first letter of input --> 'x'
Does '*' == 'x'  --> false
Does 'b' == 'x'  --> false
Is '*' a wildcard --> true
If true, call function with remaining key & input

Enter Function with key='*b?c' and input='bwc'
Retrieve first letter of key --> '*'
Retrieve second letter of key --> 'b' //if first is a wildcard, get a second
Retrieve first letter of input --> 'b'
Does '*' == 'x'  --> false
Does 'b' == 'b'  --> true
If true, call function with remaining key & input //when you match the letter after the wildcard you send the key with both the wildcard and matching letter removed
//Also, a key note here, in more complex cases, you may need to keep iterating on the wildcard even after the first match for the following letter is found

Enter Function with key='?c' and input='wc'
Retrieve first letter of key --> '?'
Retrieve first letter of input --> 'w'
If true, call function with remaining key & input // I've defined ? to match any single character, it just goes through with removing the a letter from key and input

Enter Function with key='c' and input='c'
Retrieve first letter of key --> 'c'
Retrieve first letter of input --> 'c'
Does 'c' == 'c'  --> true
If true, call function with remaining key & input

Enter Function with key='' and input=''
Return true

Sorry for the huge example, but for really getting the idea of recursion I think it's important. You'll notice, every step my 'input' got smaller, putting me one step closer to solving my problem. That's the whole idea behind recursion.

Now on to sorting by recursion. I prefer the bubble sort, so that's what I've chosen to show here today. A bubble sort is neat because it's implemented with both recursion and iteration. Here's my example:

public class test {
    public static void main (String[] args) {
        int[] a = {1,4,2,2,1};
        a = sort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.println("" + a[i]);
        }
    }
    public static int[] sort(int[] a) {
        int temp;
        boolean sorted = true;
        int[] ret = a;
        for (int i = 0; i < a.length - 1; i++) {
            if (ret[i] > ret[i+1]) {
                temp = ret[i];
                ret[i] = ret[i+1];
                ret[i+1] = temp;
                sorted = false;
            }
        }
        if (sorted) {
            return ret;
        } else {
            return sort(ret);
        }
    }
}

Let's take a look at what's going on here:

1. We start with our array at 1,4,2,2,1.
2. After the first time through our sort function we end up with 1,2,2,1,4.
3. We changed the ordering (so we're not sorted), and we have to call the function again.
4. Second time in we have 1,2,2,1,4 and we end up with 1,2,1,2,4.
5. We changed the ordering (so we're not sorted), and we have to call the function again.
6. Third time in we have 1,2,1,2,4 and we end up with 1,1,2,2,4.
7. We changed the ordering (so we're not sorted), and we have to call the function again.
8. Fourth time in we have 1,1,2,2,4 and we end up with 1,1,2,2,4.
9. We didn't change the order (we're sorted!). Return the sorted array.

I hope that this helped you out in your quest for understanding recursion. Please feel free to write comments if you would like further clarification on something I mentioned.

Answer 2

Merge sorting lends itself to recursion since it involves breaking an array in half multiple times until each piece contains two items and then sorting the small pieces and merging them back together. http://en.wikipedia.org/wiki/Merge_sort

Answer 3

To write a recursive algorithm, you need to think along these lines: How can I solve the problem by solving one or more smaller instances of the same problem? For a problem like "sort an array of N integers", the smaller problem could be an array of N-1 integers, or it could be two arrays of N/2 integers (roughly), or other possibilities.

Since you weren't give any other hints, the simplest thing would be: OK, I have an array of N integers. Let's say I sorted the last N-1 integers, so that my array would look like

------------------------------------------------|
| a[0]         | a[1] | a[2] | ...... | a[N-1]  |
------------------------------------------------|
| out of order | ......... all sorted ......... | 

If you could do that, then since you only have one out-of-order element, you should be able to figure out how to swap elements to get a[0] in the right place.

So now the outline of a method looks like this:

void sort(int[] a, int i) {   // sort the elements from a[i] to a[N-1]
    if (i <= a.length - 2) {
        // Solve the smaller problem recursively.  But if the smaller problem is
        // only 0 or 1 elements, there's nothing else to do.
        sort (a, i + 1);      
    }
    // At this point, we've sorted elements from a[i+1] to a[N-1].  Now a[i] is
    // out of order; write logic that exchanges elements to get a[i] in the right
    // place.
}

Another possible approach: Instead of sorting the N-1 elements first, you could find the smallest element, move it to the beginning of the array, so that your array looks like

--------------------------------------------|
| a[0]     | a[1] | a[2] | ...... | a[N-1]  |
--------------------------------------------|
| in order | ........ out of order ........ | 

and then call the method recursively to sort the N-1 elements a[1] to a[N-1], and then you're done.

I think you started out on the right track; you just need to visualize the problem in the correct way, which takes a little practice.