Faits: A. Le 16 juin 2011, A._, ressortissant algérien, a été arrêté après la découverte à son domicile genevois d'environ 1 kg de cocaïne, 36 g de haschich, sept téléphones portables et diverses cartes SIM. Prévenu d'infraction grave à la loi fédérale sur les stupéfiants et de recel, il a été placé en détention provisoire par le Tribunal des mesures de contrainte du canton de Genève (ci-après: le Tmc), qui a retenu qu'il existait des risques de collusion et de récidive. Par décision du 16 septembre 2011, le Tmc a autorisé la prolongation de la détention provisoire jusqu'au 16 novembre 2011. Il a estimé qu'il existait un faible risque de fuite et un risque concret de réitération. Aucune mesure de substitution n'entrait en considération. A._ a recouru contre cette décision 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), qui a rejeté ce recours par arrêt du 12 octobre 2011. En substance, cette autorité a considéré que le risque de récidive était élevé et que le recourant présentait également un risque de fuite, qui ne pouvait pas être paré par les mesures de substitution prévues à l'art. 237 du code de procédure pénale suisse (CPP; RS 312.0). B. 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é immédiate, subsidiairement d'ordonner sa libération assortie de mesures de substitution. Il requiert en outre l'assistance judiciaire. Le Ministère public du canton de Genève a présenté des observations, concluant au rejet du recours. La Cour de justice a renoncé à se déterminer. Le recourant a présenté des observations complémentaires.