Examples of sophisticated recursive algorithms

Question

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?

Answer 1

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.

Answer 2

The recursion that I used in my paper "A linear-time algorithm for computing the Voronoi diagram of a convex polygon" by Aggarwal et al is also quite complicated.

Here is a description of the algorithm from our paper. In case it's not clear from the description, in step 3 the red points are partitioned into crimson and garnet points. Steps 1, 3, and 6 are all linear time. We also know that if $n$ is the total number of points, $|\mathrm{B}| \geq \alpha n$, $|\mathrm{R}| \geq \beta n$, and $|\mathrm{C}| \geq \gamma n$ for some $\alpha, \beta, \gamma > 0$.

I'll let you figure out why the entire algorithm takes linear time.

1. Partition the original points into the blue and red sets B and R.
2. Recursively compute the convex hull of the blue points.
3. Using the structure of the blue hull, select the crimson points C.
4. Add the crimson points to the blue hull one at a time.
5. Recursively compute the convex hull of the garnet points G.
6. Merge this garnet hull with the expanded blue hull of step 4.

What makes the algorithm linear is the ability to add a fixed fraction of the red points to the blue hull at constant cost per point. The points added are the crimson points.

The recursion is thus $$ T(n) = T(|B|) + T(|G|) + O(n) $$ where you don't know $|B|$ and $|G|$ but are guaranteed that $|B| + |G| \leq (1-\gamma) n$.

Answer 3

There is a variation on the median finding recurrence that comes from range searching with halfplanes. The recurrence itself is of the form

\[ T(n) = T(n/2) + T(n/4) + cn \] which is similar to the median-finding recurrence. For more on this, look at Jeff Erickson's lecture notes and in particular Section 4.

Answer 4

There are a bunch of cool recursive algorithms [1], [2] used in RNA secondary structure prediction. Left to its own devices, a strand of RNA will form base pairs with itself; one relatively simple example from [3] computes the maximum number of nested, paired bases an RNA string will form with itself:

$M(i,j)=\underset{i\leq k < j - L_{min}}{max} \begin{cases} M(i,k-1)+ M(k+1, j-1)+1 \\M(i, j-1) \end{cases}$

---

1. Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information by M. Zuker, P. Stiegler (1981)

2. A Dynamic Programming Algorithm for RNA Structure Prediction Including Pseudoknots by E. Rivas, S. R. Eddy (1999)

3. Fast algorithm for predicting the secondary structure of single-stranded RNA by R. Nussinov, A. B. Jacobson (1980)

Answer 5

I still don't really understand what you mean by "sophisticated recursion". For example, the recursion step in the FFT algorithm is sophisticated!

But if you want to look for more complicated recursion, then mutual recursion might be one possible answer. Mutual recursion is useful when working with fuctional programming languages. Mutual recursion is the key feature of recursive descent parsers.

Answer 6

Off the top of my head, the McCarthy 91 function

F(N) = 
    n - 100    if n > 100
    F(F(n+11)) if n <= 100

and the Ackermann function

A(m, n) = 
    n + 1             if m = 0
    A(m-1, 1)         if m > 0 and n = 0
    A(m-1, A(m, n-1)) if m > 0 and n > 0

might count as offbeat, albeit toy-ish, recursive functions.