1. ## 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;
}

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