Recursive Bubble Sort

Give the recursive implementation of the Bubble Sort algorithm
Solution:
We have already discussed the Bubble sort algorithm and its optimizations in this post. The iterative algorithm for bubble sort is shown below:

void bubbleSort(int *arr, int n)
{
  for(int i=0; i<n-1; i++)
  {
    for(int j=0; j<n-i-1; j++) { if(arr[j] > arr[j+1])
        swap(&arr[j], &arr[j+1]);
    }
  }
}

The swap function is a normal swap function:

void swap(int* a, int* b)
{
  int temp = *a;
  *a = *b;
  *b = temp;
}

This function takes O(n2) time and constant extra memory. In the recursive implementation, the function is supposed to perform one small task and rest is left for the recursive call. Let us define the recursion as below:

If there are n elements in the array, then the first function instance will move the largest element (out of these n elements) to the last position of the array (a single pass of bubble sort) and then call the same function to sort the array of first n-1 elements.
The responsibility of sorting first n-1 elements is given to the recursive function call.
Code:

void bubbleSort(int *arr, int n)
{
  // TERMINATING CONDITION OF RECURSION
  if(n <= 1){ return; }
  // MOVE THE LARGEST ELEMENT AT THE END
  for(int j=0; j arr[j+1])
      swap(&arr[j], &arr[j+1]);
  }
  // CALL FUN RECURSIVELY TO SORT FIRST n-1 ELEMENTS
  bubbleSort(arr, n-1);
}

Note that this recursive solution is not better than the iterative solution in any way. In fact, it is worse, because it takes O(n) extra space also along with multiple function calls.