The complexity, nonlinearity and nonstationarity of the cardiovascular system typically defy comprehensive and deterministic mathematical modeling, except from a statistical perspective. Living systems are governed by numerous, continuously changing, interacting variables in the presence of noise. Cardiovascular signals can be shown to be discontinuous alternations between deterministic trajectories and stochastic pauses (terminal dynamics). One promising approach for assessing such nondeterministic complexity is recurrence quantification analysis (RQA). As reviewed in this paper, strategies implementing quantification of recurrences have been successful in diagnosing changes in nonstationary cardiac signals not easily detected by traditional methods. It is concluded that recurrence quantification analysis is a powerful discriminatory tool which, when properly applied to cardiac signals, can provide objectivity regarding the degree of determinism characterizing the system, state changes, as well as degrees of complexity and/or randomness.