  We consider the language of $\Delta_0$-formulas with list terms interpreted
over hereditarily finite list superstructures. We study the complexity of
reasoning in extensions of the language of $\Delta_0$-formulas with
non-standard list terms, which represent bounded list search, bounded
iteration, and bounded recursion. We prove a number of results on the
complexity of model checking and satisfiability for these formulas. In
particular, we show that the set of $\Delta_0$-formulas with bounded recursive
terms true in a given list superstructure $HW(\mathcal{M})$ is non-elementary
(it contains the class kEXPTIME, for all $k\geqslant 1$). For
$\Delta_0$-formulas with restrictions on the usage of iterative and recursive
terms, we show lower complexity.
