Examples of sophisticated recursive algorithms
My favorite recurrence shows up in output-sensitive algorithms for computing convex hulls, first by Kirkpatrick and Seidel, but later repeated by others.  Let $T(n,h)$ denote the time to compute the convex hull of $n$ points in the plane, when the convex hull has $h$ vertices.  (The value of $h$ is not known in advance, aside from the trivial bound $h\le n$.)  Kirkpatrick and Seidel's algorithm yields the recurrence
$$
  T(n,h) = \begin{cases}
       O(n) &amp; \text{if }n \le 3 \text{ or } h \le 3 \\
       T(n_1, h_1) + T(n_2, h_2) + O(n) &amp; \text{otherwise}
  \end{cases}
$$
where $n_1, n_2 \le 3n/4$ and $n_1 + n_2 = n$ and $h_1 + h_2 = h$.

The solution is $T(n,h) = O(n\log h)$.  This is a little surprising, since $h$ is not the parameter being split evenly.  But in fact, the worst case of the recurrence happens when $h_1$ and $h_2$ are both about $h/2$; if somehow magically $h_1$ is always constant, the solution would be $T(n,h) = O(n)$.

I used a variant of this recurrence in one of my first computational topology papers:
$$
  T(n,g) = \begin{cases}
       O(n) &amp; \text{if }n \le 3 \text{ or } g = 0\\
       T(n_1, g_1) + T(n_2, g_2) + O(\min\{n_1, n_2\}) &amp; \text{otherwise}
  \end{cases}
$$
where $n_1 + n_2 = n$ and $g_1 + g_2 = g$.  Again, the solution is $O(n\log g)$, and the worst case occurs when both $n$ and $g$ are always split evenly.