  We propose a new framework called recursive lattice reduction for finding
short non-zero vectors in a lattice or for finding dense sublattices of a
lattice. At a high level, the framework works by recursively searching for
dense sublattices of dense sublattices (or their duals). Eventually, the
procedure encounters a recursive call on a lattice $\mathcal{L}$ with
relatively low rank $k$, at which point we simply use a known algorithm to find
a short non-zero vector in $\mathcal{L}$. We view our framework as
complementary to basis reduction algorithms, which similarly work to reduce an
$n$-dimensional lattice problem with some approximation factor $\gamma$ to an
exact lattice problem in dimension $k < n$, with a tradeoff between $\gamma$,
$n$, and $k$. Our framework provides an alternative and arguably simpler
perspective, which in particular can be described without explicitly
referencing any specific basis of the lattice, Gram-Schmidt vectors, or even
projection (though implementations of algorithms in this framework will likely
make use of such things). We present a number of specific instantiations of our
framework. Our main concrete result is a reduction that matches the tradeoff
between $\gamma$, $n$, and $k$ achieved by the best-known basis reduction
algorithms (in terms of the Hermite factor, up to low-order terms) across all
parameter regimes. In fact, this reduction also can be used to find dense
sublattices with any rank $\ell$ satisfying $\min\{\ell,n-\ell\} \leq n-k+1$,
using only an oracle for SVP (or even just Hermite SVP) in $k$ dimensions,
which is itself a novel result (as far as the authors know). We also show a
very simple reduction that achieves the same tradeoff in quasipolynomial time.
Finally, we present an automated approach for searching for algorithms in this
framework that (provably) achieve better approximations with fewer oracle
calls.
