CLRS Exercise 2.3-4: Recursive Insertion Sort
The implementation looks fine to me, but writing the recurrence with a big theta isn't right. The problem is that the time taken to insert item \$n\$ into the right place among items 1 to \$n-1\$ depends on the values of the items — if item \$n\$ is bigger than all of items 1 to \$n-1\$ then it takes constant time to "insert" it. What we can say is that in the worst case it takes time proportional to \$n\$ to insert the item.

Let's go back and try again from first principles. If you look at the analysis of the iterative version of the insertion sort algorithm (on pages 25–6 of CLRS) you'll see that the approach the authors take is to annotate each line of code with a cost and number of times it is executed. So let's do that for the code in the post:

                                        COST    TIMES
--------------------------------------  ------  ------
def recursive_insertion_sort(A, n):
    if n &lt; 1:                           c1      1
        return A
    recursive_insertion_sort(A, n - 1)  T(n-1)  1
    key = A[n]                          c2      1
    while n &gt; 0 and key &lt; A[n - 1]:     c3      t(n) + 1
        A[n] = A[n - 1]                 c4      t(n)
        n -= 1                          c5      t(n)
    A[n] = key                          c6      1
    return A                            c7      1


Here \$t(n)\$ is the number of times that the while loop needs to be iterated when the function is called with the value \$n\$. This depends on the input A, so we might need to make separate worst-case and best-case analyses (as you can see the authors do for the iterative version on page 26).

So we have $$ T(n) = T(n-1) + c_1 + c_2 + c_3 + c_6 + c_7 + (c_3 + c_4 + c_5)t(n) $$ Now, in the best case, the input is already sorted, and so the while loop is never executed, and so \$t(n) = 0\$, hence $$ T(n) \ge T(n-1) + c_1 + c_2 + c_3 + c_6 + c_7 $$ and following similar analysis to page 26, we find $$ T(n) \ge (c_1 + c_2 + c_3 + c_6 + c_7)n $$ and so \$T(n) = \Omega(n)\$.

In the worst case, the input is sorted in reverse order, and so \$t(n) = n-1\$, hence  $$ T(n) \le T(n-1) + c_1 + c_2 + c_3 + c_6 + c_7 + (n-1)(c_3 + c_4 + c_5) $$ and again following similar analysis to page 27, we find $$ \eqalign{ T(n) &amp;\le (c_1 + c_2 + c_3 + c_6 + c_7)n + {c_3 + c_4 + c_5\over2}n(n-1) \\ &amp;= {c_3 + c_4 + c_5\over2}n^2 + \left(c_1 + c_2 + c_3 + c_6 + c_7 - {c_3\over2} - {c_4\over2} - {c_5\over2}\right)n} $$ and so \$T(n) = O(n^2)\$.

So this is an algorithm for which we can't find a big-Theta expression for the runtime — it's bounded below by \$ \Omega(n) \$ and above by \$O(n^2)\$ and these do not meet in the middle.

(There are various ways to take shortcuts in this kind of analysis, especially if you are only interested in the asymptotic result, but when you are starting out, it's good to go through all the details so that you have confidence you're not missing anything.)