Examples of sophisticated recursive algorithms

I was explaining the famous deterministic linear-time selection algorithm (median of medians algorithm) to a friend.

The recursion in this algorithm (while being very simple) is quite sophisticated. There are two recursive calls, each with different parameters.

I was trying to find other examples of such interesting recursive algorithms, but could not find any. All of the recursive algorithms I could come up with are either simple tail-recursions or simple divide and conquer (where the two calls are "the same").

Can you give some examples of sophisticated recursion?

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) & \text{if }n \le 3 \text{ or } h \le 3 \\
T(n_1, h_1) + T(n_2, h_2) + O(n) & \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) & \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\}) & \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.

StackExchange Computer Science Q#923, answer score: 15