Recursive implementation of Insertion Sort

We discussed Insertion sort in detail earlier. This post shows the recursive implementation of Insertion Sort.
Insertion sort comes under the category of online sorting algorithms, it means that it can sort the list as it receives it. Consider a situation where elements are coming and we need to maintain a sorted array of all the elements received till now. This is a fit case for insertion sort. If we do not know the number of elements coming in, we may choose to use linked list in place of arrays.
The algorithm of insertion sort can also be written recursively. Recursion does not have any performance or memory advantage, in fact, recursive code usually takes more time and more memory than corresponding non-recursive code and is not advisable to write. But, recursion in itself is such a powerful tool that every developer should be very comfortable with the approach, and interviewer may ask you to implement recursive code.
We need to define two things, the recursion, where function is defined in terms of itself and the terminating condition. Recursion for insertion sort can be defined as below

insertionSort(arr, n) = insertionSort(arr, n-1) +
                        shifting nth element to its right position.

It literally means, sort first n-1 elements using recursion and then move the last element (arr[n-1]) to its right position using the logic discussed in Code 6.1. The terminating condition for recursion is when n is equal to 1.

void insertionSortRec(int *a, int n)
{
    // TERMINATING CONDITION
    if(n <= 1){ return; }
    // SORT FIRST n-1 ELEMENTS RECURSIVELY
    insertionSortRecursive( arr, n-1 );
    // MOVING LAST ELEMENT TO IT'S RIGHT POSITION
    int j, temp = arr[n-1];
    for(j=n-2; j>=0 && a[j] > temp; j--)
        arr[j+1] = arr[j];
    arr[j+1] = temp;
}

This code takes O(n²) time and O(n) memory.