We develop a technique to compute asymptotic expansions for recurrent sequences of the form $a_{n+1}=f(a_n)$, where $f(x)=x-ax^{\alpha}+bx^{\beta} +o(x^{\beta})$ as $x\rightarrow 0$, for some real numbers $\alpha, \beta$, $a$, and $b$ satisfying $a>0$, $1<\alpha<\beta $. We prove a result which summarizes the present stage of our investigation, generalizing the expansions in [Amer. Math Monthly, Problem E $3034[1984,58]$, Solution $[1986,739]$]. One can apply our technique, for instance, to obtain the formula: $\displaystyle a_{n}={\sqrt{3}\over \sqrt{n}}- {3\sqrt{3}\over10}{\ln n \over n\sqrt{n}}+{9\sqrt{3}\over 50}{\ln n\over n^2\sqrt{n}} +o\left({\ln n\over n^{5/2}}\right)$, where $a_{n+1}=\sin(a_{n})$, $a_1\in \RR$. Moreover, we consider the recurrences $a_{n+1}=a_n^2+g_n$, and we prove that under some technical assumptions, $a_n$ is almost doubly-exponential, namely $a_n=\lfloor{k^{2^n}}\rfloor$, $a_n=\lfloor{k^{2^n}}\rfloor+1$, $a_n=\lfloor{k^{2^n}-\frac{1}{2}}\rfloor$, or $a_n=\lfloor{k^{2^n}+\frac{5}{2}}\rfloor$ for some real number $k$, generalizing a result of Aho and Sloane [Fibonacci Quart. 11 (1973), 429--437].