We propose martingale central limit theorems as an tool to prove asymptotic normality of the costs of certain recursive algorithms which are subjected to random input data. The recursive algorithms that we have in mind are such that if input data of size N produce random costs LN, then LN=D Ln+ LN-n+RN for N ≥ n0≥2, where n follows a certain distribution PN on the integers {0, … ,N} and Lk =D Lk for k≥0. Ln, LN-n and RN are independent, conditional on n, and RN are random variables, which may also depend on n, corresponding to the cost of splitting the input data of size N (into subsets of size n and N-n) and combining the results of the recursive calls to yield the overall result. We construct a martingale difference array with rows converging to ZN:= [LN - E LN] / [√Var LN]. Under certain compatibility assumptions on the sequence (PN)N≥0 we show that a pair of sufficient conditions (of Lyapunov type) for ZN → DN(0,1) can be restated as a pair of conditions regarding asymptotic relations between three sequences. All these sequences satisfy the same type of linear equation, that is also the defining equation for the sequence (E LN)N≥0 and thus very likely a well studied object. In the case that the PN are binomial distributions with the same parameter p, and for deterministic RN, we demonstrate the power of this approach. We derive very general sufficient conditions in terms of the sequence (RN)N≥0 (and for the scale RN=Nα a characterization of those α) leading to asymptotic normality of ZN.