Understanding Recursion (applying it on Bubble Sort)

Question

I am trying to figure out how to use recursion in programs. I understand how recursion works in classical examples like "factorial", but am not sure how to apply it on my own...

I am starting out with converting an iterative bubble sort code into a recursive code... I have searched over the net for the same.... but am not able to find a convincing solution/explanation..

Example iterative code for bubble sort is:

arr[n]-> array with elements (1..n) which is to be sorted

for(i:1 to n)  
    for(j:1 to n-1)  
      if(arr[j+1]>arr[j])  
         swap(arr[j+1],arr[j]);

Would feel helpful if someone could give a hint about how to go about...

Answer 1

Recursion is a design technique based on inductive proofs. Considers one or more base (simple) case(s) for your problem, and one or more ways to move the problem closer to being a base-case problem. Then, at each step of the algorithm, you either recognize completion (and deal appropriately with a base case) make the problem slightly closer to being a base case.

Bubble sort is just an application of the observation that a sorted array has all adjacent pairs of elements in order. Defined recursively, it works like:

1. Base case: There's an array of size 1 (or less) to sort. It's sorted, of course.
2. Inductive case: Bubble the largest element to the top of the array. Now there's a one-element smaller array to sort, which do.

You can write that very idea in the programming language of your choice, and you get bubble sort. Oh, but you have to define what it means to "bubble the largest element". Well, that's another opportunity for recursive design. I think you get the idea, though.

Faster sorts are mostly based on observations about how you get closer to the goal in less work. Quick sort, for instance, relies on the notion that, if an array is sorted, then there is some element P, and all elements less than P are to P's left, and all elements more than P are to P's right. If you can establish that property on an array, and also pick P, then you can cut the problem roughly in half at each step instead of simply by one.

Answer 2

public void sort(int[] arr, int first, int last){

    if(first < last && last > 0){
        if(arr[first] > arr[first+1]){
            int temp = arr[first];
            arr[first] = arr[first+1];
            arr[first+1] = temp;
        }
        sort(arr, first+1, last);
        sort(arr, first, last-1);
    }
    else
        return;
}

Late for 2 years, but maybe it will useful to someone

Answer 3

Here is another easy way to sort your array recursively using Bubble-Sort.

static void recursive_bubble_sort(int[] Arr, int l)
{// 'Arr' is the array where 'l' is the length of the array

    if (l == 0) {
       return;
    }

    for (int j = 0; j < l - 1; j++) {
        if (Arr[j] > Arr[j + 1]) {
            swap(Arr[j], Arr[j + 1]);
        }
    }

    recursive_bubble_sort(Arr, l - 1);
}

For recursive solution, the length must be updated so function always works with the remaining items from array.