14
$\begingroup$

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?

$\endgroup$

migrated from cstheory.stackexchange.com Mar 31 '12 at 20:34

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\begingroup$ Traversing a maze or more generally a graph with a breadth-first search is a simple example of an interesting recursion. $\endgroup$ – utdiscant Mar 31 '12 at 20:34
  • $\begingroup$ utdiscant, I think that BFS does not qualify for my question, as it can easily and naturally be implemented using a queue and a while loop. $\endgroup$ – elektronaj Mar 31 '12 at 20:51
  • $\begingroup$ What about backtracking in solving puzzles and parsing? And Ranking and Unranking Algorithms have non-standard recursions too. $\endgroup$ – uli Mar 31 '12 at 21:00
  • $\begingroup$ Memoization algorithms? $\endgroup$ – Kaveh Mar 31 '12 at 22:23
  • 2
    $\begingroup$ @vzn: A queue can not replace a stack. BFS is a special case. $\endgroup$ – Raphael Apr 2 '12 at 5:58
15
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I have problems with condition "if $n=O(1)$ or $h=O(1)$"; what does $O$ mean here? Are there globally bounding constants that $n$ and $h$ have to undercut to end up in case one (and the authors do not bother to give them). Because if I read it literally (i.e. interpret both $O(1)$ in the same way as $O(n)$ in the same row) case two does never or always happen (I'm not even sure). Abuse of notation taken too far, imho. $\endgroup$ – Raphael Apr 1 '12 at 10:29
  • 1
    $\begingroup$ Sorry, I've edited my answer to clarify. $O(1)$ meant "your favorite constant". I've used $3$ in my revision, but $10^{10^{100}!}$ would have worked just as well. $\endgroup$ – JeffE Apr 1 '12 at 16:04
  • $\begingroup$ How did you draw those diagrams in the computational topology papers? $\endgroup$ – user119264 May 25 '14 at 1:15
12
$\begingroup$

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$.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ A related one proposed here is quite intricate as it sports three mutually dependent (dynamic programming) recursions. $\endgroup$ – Raphael Apr 2 '12 at 9:19
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Well, the recursion in FFT (simplest form of Cooley-Tukey) is "standard" divide and conquer. This is apparent from its O(nlogn) complexity. The 2 recursive calls (1 for the even, 1 for the odds) are somewhat "same". $\endgroup$ – elektronaj Apr 2 '12 at 1:57
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.