$[5$ points$]$ Exercise $2\mathrm{.}3-5($Recursive insertion sort$)$: You can also think of insertion sort as a recursive algorithm. The basic idea for a recursive approach is as follows: a$.$ The base case is when we have $1$ element, where we have to do nothing as it is sorted by default. b$.$ In order to sort $\backslash ($ A$[1$: n$]\backslash ),$ recursively sort the subarray $\backslash ($ A$[1$: n$-1]\backslash )$ and then insert $\backslash ($ A$[$n$]\backslash )$ into the sorted subarray $\backslash ($ A$[1$: n$-1]\backslash ).$ Write the pseudocode for a recursive version of insertion sort. Give a recurrence for its worst$-$case running time. $[$Extra credit: Solve the recurrence to get a closed form for the worst$-$case runtime$]$