A difference in complexity between recursion and tail recursion (Q519902)

Two types of recursive programs over abstract structures are considered in this paper -- the most general recursive programs and tail recursive programs (which are equivalent to iterative programs). There are structures over which these two types determine one and the same class of computable functions. However, is the price of the computations one and the same? The author answers this question negatively. He presents an example of an abstract structure, over which recursive and tail recursive definitions have the same expressive power. At the same time, a function over this structure is constructed that is computed by a general recursive program more efficiently than by any tail recursive program with respect to some natural complexity measure.