Abstract: Many random combinatorial structures have recursive properties which enable the analysis by means of distributional identities connecting structures of different size. The talk will focus on certain examples of such structures: coalescent graphs, regenerative compositions and recursive trees. We focus on the asymptotic behaviour of the moments and distributions for some most characteristic quantities like e.g. the number of collision events in a coalescent process or a number of components in a random partition. Our approach to study the distributional identities is based on a combination of probabilistic and analytic tools from the theory of Markov processes and regular variation.