Faits : A. Par ordonnance pénale du 20 mars 2016, A._ a été condamné à une peine privative de liberté de 75 jours pour vol (art. 139 ch. 1 CP) et séjour illégal (art. 115 al. 1 let. b de la loi fédérale du 16 décembre 2005 sur les étrangers); par ailleurs, le sursis accordé le 30 mai 2015 à la peine pécuniaire de 90 jours-amende à 30 fr. le jour, pour séjour illégal et recel, a été révoqué. Le 21 mars 2016, A._ a formé opposition contre cette décision. Par courrier du 19 mai 2016, il a requis l'octroi de l'assistance judiciaire ainsi que la nomination de son mandataire en tant qu'avocat d'office. Cette requête a été rejetée le 25 mai 2016 par le Ministère public au motif que la cause ne présentait pas de difficultés particulières juridiques ou de fait. Par ordonnance sur opposition datée du 8 juillet 2016, le Ministère public a maintenu son prononcé du 20 mars 2016 et a transmis la cause au Tribunal de police, sa décision valant acte d'accusation. B. Le 3 août 2016, la Chambre pénale de recours de la Cour de justice de la République et canton de Genève a rejeté le recours intenté par A._ contre la décision de refus de lui octroyer l'assistance judiciaire. En substance, elle a considéré que les conditions d'une défense obligatoire (art. 130 let. c CPP) n'était pas réalisées; une défense d'office (art. 132 al. 1 let. b CP) ne s'imposait pas non plus puisque la cause n'était pas complexe. C. Agissant par la voie du recours en matière pénale, A._ demande au Tribunal fédéral d'annuler cet arrêt, de lui accorder l'assistance judiciaire gratuite et la désignation d'un avocat d'office pour la procédure cantonale. A titre subsidiaire, il conclut au renvoi de la cause au Ministère public afin qu'il lui accorde l'assistance judiciaire. En outre, il sollicite également celle-ci pour la présente procédure. La Cour de justice renonce à déposer des observations et se réfère aux considérants de son arrêt. Quant au Ministère public, il conclut au rejet du recours aux termes de ses déterminations.