While programs operating on integers are akin to integer
transition systems (ITSs), programs operating on data structures
can be transformed to term rewrite systems (TRSs) in many
cases. In the last years, powerful complexity analysis techniques
for ITSs have been developed. To make them available for the
analysis of programs operating on data structures, we present a
suitable transformation from TRSs to ITSs. It first uses a novel
sufficient criterion to prove that, independently of the
evaluation strategy under consideration, the complexity of the
analyzed TRS is bounded by its complexity w.r.t. eager
evaluation. Next, the TRS is transformed into a recursive program
over the natural numbers. As ITSs are restricted to tail
recursion, we then show how to analyze the resulting recursive
program iteratively. In each iteration, a tail-recursive function
is analyzed by existing complexity analysis tools for ITSs. Then,
calls to this function are eliminated, so that non-tail-recursive
program parts become tail-recursive and can be analyzed in the
next iteration.