插入排序介绍：

从第二个数开始遍历数组，将该数据A[i]与前面的数据依次进行比较，直到找到合适的位置

A其中，每一次比较未找到合适的位置时，被比较过的数据都会向后移一位，最后将A[i]放到属于它的位置

递归的操作在与将A[n]放入已经被排列好的数组A[n-1]中，以此类推

//用递归做插入排序
//从小到大 
Sort(A,j) 
if (j>0)
return Sort(A,j-1);
i=j-1;
key=A[j];
while i>0&&A[i]>key
    A[i+1]=A[i];
    i--;
A[i+1]=key; 

不过，递归是课后题，个人觉得插入排序没必要用递归，以下为书中没有使用递归时的伪代码，欢迎大家在评论区讨论。