  A {\it scenery} is a coloring $\xi$ of the integers. Let $\{S_t\}_{t\geq 0}$
be a recurrent random walk on the integers. Observing the scenery $\xi$ along
the path of this random walk, one sees the color $\chi_t:=\xi(S_t)$ at time
$t$. The {\it scenery reconstruction problem} is concerned with recovering the
scenery $\xi$, given only the sequence of observations $\chi:=(\chi_t)_{t\geq
0}$. The scenery reconstruction methods presented to date require the random
walk to have bounded increments. Here, we present a new approach for random
walks with unbounded increments which works when the tail of the increment
distribution decays exponentially fast enough and the scenery has five colors.
