Faits: A. A._, ressortissant français résidant à Marseille, a été arrêté à Genève le 22 octobre 2011 à 13h00, alors qu'il quittait la succursale d'une banque en compagnie de B._. La police avait été alertée le jour même peu après midi par le responsable de la sécurité de cette banque, qui avait signalé que ces deux individus avaient été dénoncés pour avoir commis un vol astucieux la veille au soir et qu'ils semblaient sévir à nouveau dans cette succursale. Lors de son interpellation, A._ avait sur lui la somme de 3'890 euros. Son comparse, qui avait sur lui 4'253,70 euros et qui dissimulait des cartes bancaires dans son slip, a aussitôt admis avoir commis un vol à l'astuce la veille et trois autres peu avant. L'avis d'arrestation mentionne que les prénommés ont été interpellés "en flagrant délit (art. 217 al. 1 let. a CPP) de vol à la tire". Le 23 octobre 2011, le Ministère public du canton de Genève (ci-après: le Ministère public) a ordonné l'ouverture d'une instruction pénale contre A._ et B._ pour vol et utilisation frauduleuse d'un ordinateur. Il a également ordonné la reprise d'une instruction portant sur des vols à l'astuce commis en septembre 2011, A._ apparaissant sur les images de vidéosurveillance relatives à ces infractions. Le même jour, le Ministère public a demandé la mise en détention provisoire des intéressés. B. Par ordonnance du 24 octobre 2011, le Tribunal des mesures de contrainte du canton de Genève (ci-après: le Tmc) a ordonné la détention provisoire de A._ pour une durée d'un mois, en raison des risques de fuite et de collusion. Le prénommé a recouru contre cette ordonnance auprès de la Chambre pénale de recours de la Cour de justice du canton de Genève (ci-après: la Cour de justice), en alléguant en substance que son arrestation ne pouvait se fonder que sur l'art. 217 al. 2 CPP et que les conditions d'application de cette norme selon le droit cantonal n'étaient pas réunies. La Cour de justice a rejeté ce recours par arrêt du 4 novembre 2011. Elle a notamment considéré que l'arrestation avait bien eu lieu dans une situation de flagrant délit au sens de l'art. 217 al. 1 let. a CPP et qu'elle était au demeurant également licite au regard de l'art. 217 al. 2 CPP. C. Agissant par la voie du recours en matière pénale, A._ demande au Tribunal fédéral d'annuler cet arrêt et d'ordonner sa mise en liberté. Il requiert en outre l'octroi de l'assistance judiciaire. Le Ministère public a présenté des observations, concluant au rejet du recours. La Cour de justice a renoncé à se déterminer. Le recourant a formulé des observations complémentaires. 