  We consider a stochastic recurrence equation of the form $Z_{n+1} = A_{n+1}
Z_n+B_{n+1}$, where $\mathbb{E}[\log A_1]<0$, $\mathbb{E}[\log^+ B_1]<\infty$
and $\{(A_n,B_n)\}_{n\in\mathbb{N}}$ is an i.i.d. sequence of positive random
vectors. The stationary distribution of this Markov chain can be represented as
the distribution of the random variable $Z \triangleq \sum_{n=0}^\infty
B_{n+1}\prod_{k=1}^nA_k$. Such random variables can be found in the analysis of
probabilistic algorithms or financial mathematics, where $Z$ would be called a
stochastic perpetuity. If one interprets $-\log A_n$ as the interest rate at
time $n$, then $Z$ is the present value of a bond that generates $B_n$ unit of
money at each time point $n$. We are interested in estimating the probability
of the rare event $\{Z>x\}$, when $x$ is large; we provide a consistent
simulation estimator using state-dependent importance sampling for the case,
where $\log A_1$ is heavy-tailed and the so-called Cram\'{e}r condition is not
satisfied. Our algorithm leads to an estimator for $P(Z>x)$. We show that under
natural conditions, our estimator is strongly efficient. Furthermore, we extend
our method to the case, where $\{Z_n\}_{n\in\mathbb{N}}$ is defined via the
recursive formula $Z_{n+1}=\Psi_{n+1}(Z_n)$ and $\{\Psi_n\}_{n\in\mathbb{N}}$
is a sequence of i.i.d. random Lipschitz functions.
