  A nondecreasing sequence of positive integers is $(\alpha,\beta)$-Conolly, or
Conolly-like for short, if for every positive integer $m$ the number of times
that $m$ occurs in the sequence is $\alpha + \beta r_m$, where $r_m$ is $1$
plus the 2-adic valuation of $m$. A recurrence relation is $(\alpha,
\beta)$-Conolly if it has an $(\alpha, \beta)$-Conolly solution sequence. We
discover that Conolly-like sequences often appear as solutions to nested (or
meta-Fibonacci) recurrence relations of the form $A(n) = \sum_{i=1}^k
A(n-s_i-\sum_{j=1}^{p_i} A(n-a_{ij}))$ with appropriate initial conditions. For
any fixed integers $k$ and $p_1,p_2,\ldots, p_k$ we prove that there are only
finitely many pairs $(\alpha, \beta)$ for which $A(n)$ can be $(\alpha,
\beta)$-Conolly. For the case where $\alpha =0$ and $\beta =1$, we provide a
bijective proof using labelled infinite trees to show that, in addition to the
original Conolly recurrence, the recurrence $H(n)=H(n-H(n-2)) + H(n-3-H(n-5))$
also has the Conolly sequence as a solution. When $k=2$ and $p_1=p_2$, we
construct an example of an $(\alpha,\beta)$-Conolly recursion for every
possible ($\alpha,\beta)$ pair, thereby providing the first examples of nested
recursions with $p_i>1$ whose solutions are completely understood. Finally, in
the case where $k=2$ and $p_1=p_2$, we provide an if and only if condition for
a given nested recurrence $A(n)$ to be $(\alpha,0)$-Conolly by proving a very
general ceiling function identity.
