Recursive Insertion Sort

I managed to write the following insertion sort program but I'm meant to do it recursively. Any ideas how to do it?

#include <stdio.h>

#define N 7

int InsertionSort(int array[N])
{
int j, p;
int temp;
for(p=1;p<N;p++)
{
temp = array[p];
for(j=p;j>0 && array[j-1]>temp;j--)
array[j] = array[j-1];
array[j] = temp;
}
printf("The list of sorted numbers is\n");
for(p=0;p<N;p++)
printf("%d ",array[p]);
printf("\n\n");
return 0;
}

void main()
{
int array[N] = {37,23,17,12,72,31,46};
InsertionSort(array);
return;
}

Loops can be turned into tail recursion really easy

Code:

#include <stdio.h>

#define N 7

void InsertionSort(int i, int array[], int size)
{
    if (i < size)
    {
        int j;
        int temp = array[i];

        for (j = i; j > 0 && array[j-1] > temp; j--)
            array[j] = array[j-1];
        array[j] = temp;

        InsertionSort(++i, array, size);
    }
}

int main(void)
{
    int p;
    int array[N] = {37,23,17,12,72,31,46};

    InsertionSort(0, array, N);
    printf("The list of sorted numbers is\n");

    for (p = 0; p < N; p++)
        printf("%d ",array[p]);
    printf("\n\n");

    return 0;
}

And don't use void main, it's not valid C for a hosted implementation. In other words, if you use an operating system then main only returns an int, if you *are* the operating system, you can do what you want.