Understanding Recursion (applying it on Bubble Sort)

Question

Hello All,

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

The iterative code for bubble sort is:

arr[n]-> array with n elements which is to be sorted

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

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

Answer 1

I am not sure whether Bubblesort is a good algorithm to practice recursion on. It would be quite ugly to convert it to recursion because it's a nested cycle. It would look something like this:

function pass(i,j,n,arr)
{
  if(arr[i]>arr(j))
    swap(arr[i],arr[j]);

  if(j==n)
  {
    j=0;
    i=i+1;
  }
  if(i==n+1)
    return arr;

  return pass(i,j+1,n,arr);
}

It's the same for loop, only longer to define, using a lot more memory.

You should instead try to implement QuickSort. It needs recursion, and it's a lot faster in most cases than BubbleSort. Most platforms implemented it already, so you don't have to write it yourself, but it's good to know how it works, and it helps understand recursion.

If you want you might also try to solve this problem using recursion:
You have a table NxM of numbers, and a starting coordinate (position). It's a ^travellers^ position. The traveller can travel to an adjacent cell (right, left, up or down) which has a smaller number than the one he's on. You must write a program that computes the longest path the traveller can pass under these constraints. Use random to generate the array, or generate it manually.

Answer 2

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.