  A random walk with counterbalanced steps is a process of partial sums $\check
S(n)=\check X_1+ \cdots + \check X_n$ whose steps $\check X_n$ are given
recursively as follows. For each $n\geq 2$, with a fixed probability $p$,
$\check X_n$ is a new independent sample from some fixed law $\mu$, and with
complementary probability $1-p$, $\check X_n= -\check X_{v(n)}$ counterbalances
a previous step, with $v(n)$ a uniform random pick from $\{1, \ldots, n-1\}$.
We determine the asymptotic behavior of $\check S(n)$ in terms of $p$ and the
first two moments of $\mu$. Our approach relies on a coupling with a
reinforcement algorithm due to H.A. Simon, and on properties of random
recursive trees and Eulerian numbers, which may be of independent interest. The
method can be adapted to the situation where the step distribution $\mu$
belongs to the domain of attraction of a stable law.
