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.

Considérant en droit :
1.
Le recours en matière pénale est ouvert contre une décision incidente par laquelle l'assistance judiciaire gratuite est refusée à une partie à la procédure pénale (art. 78 al. 1 LTF). Le refus de désigner un avocat d'office est susceptible de causer au prévenu un préjudice irréparable au sens de l'art. 93 al. 1 let. a LTF, de sorte qu'il peut faire l'objet d'un recours immédiat au Tribunal fédéral (<ref-ruling> consid. 2.2 p. 205; <ref-ruling> consid. 4 p. 338 s. et les références).
Pour le surplus, le recours a été formé en temps utile (art. 46 al. 1 let. a et 100 al. 1 LTF) contre une décision rendue en dernière instance cantonale (art. 80 LTF) et les conclusions présentées sont recevables au regard de l'art. 107 al. 2 LTF. Il y a donc lieu d'entrer en matière.
2.
Le Tribunal fédéral conduit son raisonnement juridique sur la base des faits établis par l'autorité précédente (art. 105 al. 1 LTF), à moins que ceux-ci n'aient été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire de l'art. 9 Cst. (<ref-ruling> consid. 4.1.2 p. 62) - ou en violation du droit au sens de l'art. 95 LTF. Si le recourant entend s'écarter des constatations de fait de l'autorité précédente, il doit expliquer de manière circonstanciée en quoi les conditions de l'art. 105 al. 2 LTF seraient réalisées et la correction du vice susceptible d'influer sur le sort de la cause (cf. art. 97 al. 1 LTF). A défaut, il n'est pas possible de tenir compte d'un état de fait divergent de celui retenu dans l'acte attaqué. En particulier, le Tribunal fédéral n'entre pas en matière sur des critiques de type appellatoire portant sur l'état de fait ou sur l'appréciation des preuves (<ref-ruling> consid. 5.1 p. 356; <ref-ruling> consid. 3 p. 104 et les arrêts cités).
En l'espèce, au début de son écriture, le recourant présente, sur quatre pages, son propre exposé des faits. En tant que ces éléments divergent de ceux constatés dans l'arrêt cantonal et qu'ils ne sont pas critiqués sous l'angle de l'établissement arbitraire des faits examiné ci-après, il n'en sera pas tenu compte.
Le recourant se plaint d'une appréciation arbitraire des faits uniquement en tant que l'instance précédente n'aurait pas retenu que, suite à l'intervention de son avocat, le Ministère public aurait, dans son ordonnance sur opposition, motivé de manière circonstanciée le prononcé d'une courte peine privative de liberté, conformément aux exigences de motivation de l'art. 41 al. 2 CP; à ses yeux, l'ordonnance du 20 mars 2016 n'était pas suffisamment motivée sur ce point. Sa critique doit être écartée. En effet, cet élément n'apparaît pas susceptible d'influer sur le sort de la cause (cf. consid. 3.3), de sorte qu'il n'y a pas lieu de compléter l'état de fait retenu dans l'arrêt attaqué.
3.
Le recourant invoque le droit à l'assistance judiciaire tel qu'il découle des art. 132 al. 1 let. b et al. 2 CPP, 29 al. 3 Cst., 6 par. 3 let. c CEDH et 14 ch. 3 du Pacte ONU II. Il se prévaut de sa situation personnelle (nationalité étrangère; absence de domicile, de permis de séjour et de revenu; difficultés de lecture et incapacité de rédiger seul un courrier simple), ainsi que des difficultés factuelles de la cause liées à son incapacité d'exposer clairement sa situation personnelle et administrative et de fournir les preuves de ses allégations. Il soutient également que la cause présente des difficultés juridiques, telles que la question de sa responsabilité au moment des faits et l'application des circonstances atténuantes du repentir sincère (art. 48 let. c CP) ou de l'absence d'un dommage (art. 47 et 52 CP).
3.1. En dehors des cas de défense obligatoire (art. 130 CPP), l'art. 132 al. 1 let. b CPP soumet le droit à l'assistance d'un défenseur d'office aux conditions que le prévenu soit indigent et que la sauvegarde de ses intérêts justifie une telle assistance. S'agissant de la seconde condition, elle s'interprète à l'aune des critères mentionnés à l'art. 132 al. 2 et 3 CPP. Ainsi, les intérêts du prévenu justifient une défense d'office lorsque la cause n'est pas de peu de gravité et qu'elle présente, sur le plan des faits ou du droit, des difficultés que le prévenu seul ne pourrait pas surmonter (art. 132 al. 2 CPP); ces deux conditions mentionnées à l'art. 132 al. 2 CPP doivent être réunies cumulativement.
En tout état de cause, une affaire n'est pas de peu de gravité lorsque le prévenu est passible d'une peine privative de liberté de plus de quatre mois, d'une peine pécuniaire de plus de 120 jours-amende ou d'un travail d'intérêt général de plus de 480 heures (art. 132 al. 3 CPP).
Pour évaluer si l'affaire présente des difficultés que le prévenu ne pourrait pas surmonter sans l'aide d'un avocat, il y a lieu d'apprécier l'ensemble des circonstances concrètes. Il faut tenir compte notamment des capacités du prévenu, de son expérience dans le domaine juridique ainsi que des mesures qui paraissent nécessaires, dans le cas particulier, pour assurer sa défense, en particulier en ce qui concerne les preuves qu'il devra offrir (<ref-ruling> consid. 2.5.2 p. 233; <ref-ruling> consid. 4 p. 105).
3.2. Avec raison, le recourant ne prétend pas que les conditions d'une défense obligatoire selon l'art. 130 let. c CPP seraient remplies; l'instance précédente peut en effet être suivie lorsqu'elle retient que le trouble anxieux dont souffre le recourant nécessitant la prise de benzodiazépine sous contrôle médical ne l'empêche pas de défendre suffisamment ses intérêts. Comme relevé par cette autorité, les procès-verbaux de la police et du Ministère public révèlent que le recourant est capable de s'exprimer sur les faits et sur sa situation personnelle, ainsi que de demander utilement l'aide aux associations s'occupant de personnes vivant dans la précarité.
3.3. S'agissant de l'application de l'art. 132 al. 1 let. b CPP, l'instance précédente a laissé indécise la question de l'indigence du recourant. Elle a par ailleurs estimé que la cause ne semblait pas de peu de gravité dès lors que l'intéressé était exposé, sur la base de l'ordonnance pénale, à une peine privative de liberté de 75 jours, augmentée de 90 jours-amende en raison de la révocation d'un sursis accordé précédemment. Au vu du raisonnement qui va suivre, il n'est pas nécessaire d'approfondir ces questions.
En l'occurrence, il est reproché au recourant d'avoir dérobé le sac à main de la plaignante - lequel se trouvait dans sa voiture - alors qu'elle était en train de jeter des bouteilles à un point de récupération du verre. Après qu'elle aurait crié " au voleur ", le recourant lui aurait rendu son sac avant de prendre la fuite; il aurait été rattrapé par le fils de la plaignante; le recourant aurait également séjourné illégalement en Suisse. Contrairement à ce que prétend celui-ci, la cause ne présente pas, sur le plan des faits et du droit, de difficultés qu'il ne pourrait pas surmonter sans l'aide d'un avocat. Le recourant qui s'exprime en français a en effet admis les faits qui lui sont reprochés. Bien qu'il souffre d'un trouble anxieux nécessitant une médication, il a été capable de s'expliquer sur ces faits simples et leurs circonstances. Par ailleurs, l'exposé de sa situation personnelle et administrative n'apparaît pas compliqué. Le fait que certaines de ses déclarations sur sa situation soient - selon ses dires - incomplètes ou en contradiction avec des pièces du dossier ne permet pas de considérer qu'il est incapable d'assumer une défense sans l'assistance d'un avocat. Dans la mesure où le recourant s'est adressé utilement à des intervenants sociaux pour l'aider à rédiger son opposition, il ne peut être suivi lorsqu'il prétend qu'il n'aurait pas été à même de requérir seul les documents qu'il a produits dans le cadre de la procédure d'opposition (attestations du Centre social protestant et des Hôpitaux Universitaire de Genève).
Ensuite, le recourant s'efforce de démontrer que le dossier comporterait des difficultés juridiques liées à la question de sa responsabilité au moment des faits et à l'application des circonstances atténuantes du repentir sincère ou de l'infraction d'importance mineure. Ces questions ne présentent toutefois pas de difficultés particulières en l'espèce et elles constituent des questions courantes de droit pénal que tout tribunal est en mesure de traiter correctement. Enfin, le fait que le Ministère public ait, après l'intervention de l'avocat du recourant, rendu le 8 juillet 2016 une nouvelle ordonnance dans laquelle les motifs du prononcé d'une courte peine sont étayés de manière circonstanciée ne permet pas de considérer que les conditions de l'art. 132 al. 2 CPP seraient réalisées.
Dans ces circonstances, l'instance précédente n'a pas violé le droit fédéral en confirmant le refus du Ministère public d'octroyer l'assistance judiciaire au recourant.
4.
Le recours doit par conséquent être rejeté dans la mesure de sa recevabilité. Cette issue était d'emblée prévisible, ce qui conduit au rejet de la demande d'assistance judiciaire. Vu les circonstances, il sera exceptionnellement statué sans frais (art. 66 al. 1, deuxième phrase, LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté dans la mesure où il est recevable.
2.
La demande d'assistance judiciaire est rejetée.
3.
Il n'est pas perçu de frais judiciaires.
4.
Le présent arrêt est communiqué au mandataire du recourant, au Ministère public de la République et canton de Genève et à la Chambre pénale de recours de la Cour de justice de la République et canton de Genève.
Lausanne, le 22 novembre 2016
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président : Fonjallaz
La Greffière : Arn