Unconstrained face recognition is still an open problem, as state-of-the-art algorithms have not yet reached high recognition performance in real-world environments (e.g., crowd scenes at the Boston Marathon). This paper addresses this problem by proposing a new approach called Adaptive Sparse Representation of Random Patches (ASR+). In the learning stage, for each enrolled subject, a number of random patches are extracted from the subject's gallery images in order to construct representative dictionaries. In the testing stage, random test patches of the query image are extracted, and for each test patch a dictionary is built concatenating the 'best' representative dictionary of each subject. Using this adapted dictionary, each test patch is classified following the Sparse Representation Classification (SRC) methodology. Finally, the query image is classified by patch voting. Thus, our approach is able to deal with a larger degree of variability in ambient lighting, pose, expression, occlusion, face size and distance from the camera. Experiments were carried out on five widely-used face databases. Results show that ASR+ deals well with unconstrained conditions, outperforming various representative methods in the literature in many complex scenarios.