Faits :
A.
A._ a été arrêté par la police judiciaire le 28 avril 2016. Il a été mis en prévention pour corruption active (<ref-law>) et placé en détention provisoire jusqu'au 27 juin 2016, date à laquelle il a été libéré avec des mesures de substitution.
Le 29 avril 2016, le Procureur a ordonné la défense d'office du prévenu et désigné Me B._ en qualité de défenseur. Le 23 mai 2016, Me C._ a informé le Ministère public qu'il était désormais chargé d'assurer la défense de A._ en tant qu'avocat de choix. Le 24 mai 2016, le procureur a ordonné la révocation de la défense d'office accordée au prévenu.
Par courrier du 8 juillet 2016, Me Malek Adjadj a informé le Ministère public qu'il succédait à Me C._ et a joint une procuration en sa faveur signée par le prévenu. Le 29 juillet 2016, ce même avocat a sollicité sa nomination en qualité de défenseur d'office du prévenu.
B.
Par décision du 2 août 2016, le Ministère public de la République et canton de Genève a refusé de nommer un défenseur d'office à A._. Statuant sur recours du prévenu, la Chambre pénale de recours de la Cour de justice de la République et canton de Genève a confirmé cette décision par arrêt du 25 octobre 2016.
C.
A._ recourt par acte du 25 novembre 2016 contre cette décision auprès du Tribunal fédéral. Il demande l'annulation de l'arrêt attaqué et la désignation de Me Malek Adjadj en qualité de défenseur d'office dans la cause pénale dirigée contre lui. Subsidiairement, il conclut au renvoi de la cause. Il demande en outre à être mis au bénéfice de l'assistance judiciaire.
Le Ministère public conclut au rejet du recours. La cour cantonale se réfère aux considérants de son arrêt et n'a pas d'observations à formuler. Dans un second échange d'écritures, le recourant persiste dans ses conclusions.

Considérant en droit :
1.
Conformément à l'<ref-law>, une décision relative à la défense d'office dans une cause pénale peut faire l'objet d'un recours en matière pénale. Le recourant, prévenu et auteur de la demande de désignation d'un défenseur d'office, a qualité pour agir (<ref-law>). Le refus de désigner un avocat d'office au prévenu est susceptible de lui causer un préjudice irréparable au sens de l'<ref-law> (<ref-ruling> consid. 4 p. 338 et les références). Pour le surplus, le recours est formé en temps utile (<ref-law>) contre une décision rendue en dernière instance cantonale (<ref-law>) et les conclusions présentées sont recevables au regard de l'<ref-law>.
2.
Le recourant se plaint d'une violation de son droit d'être entendu du fait que la cour cantonale n'a pas examiné sa situation financière ni son grief de violation de l'interdiction du formalisme excessif. Le Ministère public considère en revanche que ces aspects étaient non décisifs pour l'issue du litige.
2.1.
2.1.1. Selon la jurisprudence, l'autorité qui ne traite pas un grief relevant de sa compétence, motivé de façon suffisante et pertinente pour l'issue du litige commet un déni de justice formel proscrit par l'art. 29 al. 1 Cst. (<ref-ruling> consid. 2.1 p. 9; <ref-ruling> consid. 3a p. 117 et les références). De même, la jurisprudence a déduit du droit d'être entendu de l'art. 29 al. 2 Cst. l'obligation pour l'autorité de motiver sa décision, afin que l'intéressé puisse se rendre compte de la portée de celle-ci et l'attaquer en connaissance de cause (<ref-ruling> consid. 2.1 p. 145; <ref-ruling> consid. 5.1 p. 237; <ref-ruling> consid. 4.2 p. 355). La motivation d'une décision est suffisante lorsque l'autorité mentionne, au moins brièvement, les motifs qui l'ont guidée et sur lesquels elle a fondé son raisonnement. L'autorité ne doit toutefois pas se prononcer sur tous les moyens des parties; elle peut se limiter aux questions décisives (<ref-ruling> consid. 4.2 p. 157; <ref-ruling> consid. 3.2 p. 270; <ref-ruling> consid. 5.2 p. 236). La motivation peut pour le reste être implicite et résulter des différents considérants de la décision (cf. arrêts 1C_167/2015 18 août 2015 consid. 3; 2C_23/2009 du 25 mai 2009 consid. 3.1, publié in RDAF 2009 II p. 434).
2.1.2. Le CPP opère une double distinction en matière de défense: d'une part entre défense facultative et défense obligatoire; d'autre part entre défense privée et défense d'office (PIQUEREZ/MACALUSO, Procédure pénale suisse, 3e édition 2011, p. 284 n. 817; <ref-ruling> consid. 4.2 p. 346).
La défense facultative laisse au prévenu le soin de décider librement s'il entend se défendre seul ou recourir aux services d'un avocat. La défense obligatoire impose en revanche au prévenu l'assistance d'un défenseur - privé ou d'office - (PIQUEREZ/MACALUSO, op. cit., ibidem; NIKLAUS OBERHOLZER, Grundzüge des Strafprozessrechts, 3e édition 2012, n° 434 ss et 445 ss). Réglée par l'<ref-law>, la défense obligatoire intervient notamment lorsque la détention provisoire, y compris la durée de l'arrestation provisoire, a excédé dix jours (let. a) et lorsque le prévenu encourt une peine privative de liberté de plus d'un an ou une mesure entraînant une privation de liberté (let. b). Elle est indépendante de la situation financière du prévenu. La défense privée est celle où l'accusé choisit librement son avocat et le rémunère lui-même.
La défense d'office est réglée par l'<ref-law> dont l'al. 1 est formulé comme suit:
"La direction de la procédure ordonne une défense d'office:
a.en cas de défense obligatoire:
1. si le prévenu, malgré l'invitation de la direction de la procédure, ne désigne pas de défenseur privé
2. si le mandat est retiré au défenseur privé ou que celui-ci a décliné le mandat et que le prévenu n'a pas désigné un nouveau défenseur dans le délai imparti;
b. si le prévenu ne dispose pas des moyens nécessaires et que l'assistance d'un défenseur est justifiée pour sauvegarder ses intérêts."
La défense d'office voit ainsi l'autorité commettre au prévenu un défenseur rétribué par l'Etat - à tout le moins provisoirement -, dans la mesure où la sauvegarde des droits de l'intéressé le requiert (PIQUEREZ/MACALUSO, op. cit., p. 284 n. 817; OBERHOLZER, op. cit., n. 445). Elle intervient lorsque le prévenu n'a pas de défenseur alors même qu'il s'agit d'un cas de défense obligatoire (al. 1 let. a ch. 1 et 2) ou lorsque le prévenu ne dispose pas des moyens nécessaires et que l'assistance d'un défenseur est justifiée pour sauvegarder ses intérêts (al. 1 let. b). La sauvegarde des intérêts du prévenu indigent justifie la commission d'une défense d'office notamment lorsque l'affaire n'est pas de peu de gravité (soit à tout le moins lorsque le prévenu est passible d'une peine privative de liberté de plus de quatre mois conformément à l'<ref-law>) et qu'elle présente des difficultés que le prévenu seul ne pourrait pas surmonter (<ref-law>).
2.2.
2.2.1. En l'espèce, il est constant que le prévenu se trouve dans un cas de défense obligatoire. Celui-ci se prévaut de la solution de l'<ref-ruling> pour faire valoir qu'il y aurait formalisme excessif à ne pas directement lui désigner son défenseur de choix comme défenseur d'office. Au vu de cette jurisprudence, il lui suffirait de résilier le mandat puis de demander la nomination d'office de son défenseur actuel. Par souci de simplification, il y aurait ainsi lieu de lui désigner directement son défenseur de choix comme défenseur d'office, sans que le prévenu doive auparavant résilier le mandat qui les lie.
L'arrêt auquel fait référence le recourant confirme que, lorsqu'un prévenu doit se voir désigner une défense d'office car il est - quel qu'en soit le motif - dépourvu de défenseur alors qu'il se trouve dans un cas de défense obligatoire (cf. <ref-law>), il y a lieu de prendre en considération ses souhaits conformément à l'<ref-law>, ce quand bien même il n'aurait pas démontré son indigence, la question de la prise en charge des coûts dans le cadre d'une défense d'office en vertu de l'<ref-law> n'ayant pas à être examinée avant la fin de la procédure (<ref-ruling>).
Les premiers juges ont considéré qu'il ne se justifiait pas d'accorder une défense d'office au recourant en vertu de l'<ref-law> tant que le recourant bénéficiait d'une défense privée. Ils n'ont pas expressément examiné le grief dénonçant un éventuel formalisme excessif. On peut certes comprendre de ce silence un rejet du grief, faute de pertinence, comme le soutient le Ministère public. En effet, le cas d'espèce se distingue de l'ATF précité en ce que, dans ce cas-là, le mandat de choix avait précisément déjà pris fin. En outre, le prévenu ne s'était pas déjà préalablement vu accorder une défense d'office. Il apparaît quoi qu'il en soit clairement que la solution défendue par le recourant équivaudrait à permettre de simplement contourner les règles relatives à la personne du défenseur d'office. Tant que, comme dans l'<ref-ruling>, il est question d'une première nomination d'office, la question de l'abus de droit ne se pose pas. Le risque est au contraire bien réel lorsque, comme en l'espèce, le prévenu a décliné une première défense d'office.
On peut en tout état laisser indécise la question de savoir si le fait de ne pas avoir examiné expressément le grief de formalisme excessif constitue une violation du droit d'être entendu du recourant ou si, vu la pertinence d'un tel grief, le simple examen de l'applicabilité (déniée) de l'<ref-law> était suffisant. Le recourant se plaint en effet également de la violation de son droit d'être entendu du fait que sa situation financière n'a pas été examinée. Or, il s'agit là d'un élément pertinent qui pourrait justifier une nouvelle nomination d'un défenseur d'office.
2.2.2. Il est en effet admis que le prévenu a volontairement renoncé à la défense d'office qui lui avait été accordée au lendemain de son arrestation. Lorsque, deux mois plus tard, le recourant a demandé à être à nouveau mis au bénéfice d'une défense d'office, il faisait valoir avoir été licencié par son employeur en raison de sa détention provisoire. En d'autres termes, il se prévalait d'une situation financière modifiée depuis le jour où il avait renoncé à la défense d'office.
En l'occurrence, la cour cantonale n'a pas examiné si une défense d'office s'imposait en vertu d'une éventuelle indigence du prévenu. Elle a en effet considéré que les conditions pour une défense d'office au sens de l'<ref-law> n'étaient pas remplies, puis s'est contentée d'exposer que "contrairement à l'opinion du recourant, il n'y a pas de place non plus pour une défense d'office au sens de l'art. 132 al. 1 let. b et al. 2 et 3 CPP, cette disposition étant applicable aux autres cas de défense d'office (gratuite), à l'exception de la défense obligatoire".
La cour cantonale n'a pas justifié cette interprétation de l'<ref-law>. Or, il n'est pas manifeste que l'<ref-law> règle exhaustivement les cas de défense obligatoire dans lesquels une défense d'office doit être ordonnée. D'un point de vue littéral, l'<ref-law> dit que la direction de la procédure ordonne une défense d'office si, en cas de défense obligatoire, le prévenu ne dispose pas d'un défenseur ou si le prévenu ne dispose pas des moyens nécessaires et que l'assistance d'un défenseur est justifiée pour sauvegarder ses intérêts. Le second cas, réglé par la lettre b, peut se comprendre tant comme excluant - a contrario de la lettre a - les cas d'office, que comme réglant les cas d'indigence de façon générale, indépendamment de la question de savoir si l'on est dans un cas de défense d'office ou non.
Le législateur n'a rien précisé à cet égard (Message du 21 décembre 2005 relatif à l'unification du droit de la procédure pénale, FF 2006 1158 ch. 2.4.3.2). Certains auteurs considèrent que, selon la systématique de la loi, l'<ref-law> règle le droit à la défense d'office dans le cadre de la défense facultative uniquement (MAURICE HARARI/TATIANA ALIBERTI, Commentaire Romand, n° 53 ad <ref-law>; Franz Riklin, StPO Kommentar, 2e éd. 2014, n° 2 ad <ref-law>). Or, d'un point de vue purement téléologique, il apparaît peu pertinent de n'accorder une défense d'office qu'au prévenu indigent qui ne remplirait pas les conditions de la défense obligatoire. On peut au contraire présumer que les cas de défense obligatoire décrits à l'<ref-law> remplissent la seconde condition de l'<ref-law>, à savoir que dans de telles hypothèses l'assistance d'un défenseur est nécessairement justifiée pour sauvegarder la défense des intérêts du prévenu (en ce sens, NIKLAUS RUCKSTUHL, Basler Kommentar, n° 3 ad <ref-law>). En d'autres termes, l'<ref-law> peut s'appliquer également à des cas de défense obligatoire autres que ceux de la let. a, notamment lorsque, comme ce peut être le cas en l'occurrence, le prévenu, qui disposait jusqu'alors d'un défenseur de choix, voit sa situation financière évoluer au point de ne plus disposer des moyens nécessaires à la rémunération de celui-ci.
Il subsiste certes un risque qu'une telle possibilité ouvre la porte à un contournement des règles légales par le prévenu qui souhaiterait, sans motif valable (cf. <ref-law>), un changement en la personne de l'avocat d'office. Il appartient toutefois à la direction de la procédure de vérifier que la situation financière du requérant a bel et bien évolué. Elle s'assurera ainsi de la bonne foi du prévenu qui avait dans un premier temps renoncé à la défense d'office. En l'occurrence, le Ministère public voit un tel abus de droit dans le fait que le prévenu a renoncé à une défense d'office au profit d'une défense privée en début de procédure. Or, vu le temps écoulé entre le moment du choix d'un défenseur privé et celui de la nouvelle demande de désignation d'office, ainsi que le changement de situation financière allégué, il s'imposait à tout le moins de procéder à un examen de la situation. En l'espèce, ni le Ministère public ni l'a cour cantonale ne l'ont fait. Il en résulte une violation du droit d'être entendu du recourant.
3.
Compte tenu de ce qui précède, le recours doit être admis et la cause renvoyée à la Cour de justice pour nouvelle décision au sens des considérants.
Le recourant obtenant gain de cause avec l'aide d'un avocat, celui-ci a droit à des dépens à la charge du canton de Genève (art. 68 al. 1 et 2 LTF). Conformément à l'<ref-law>, il n'est pas perçu de frais judiciaires. La demande d'assistance judiciaire pour la présente procédure est par conséquent sans objet.

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis. L'arrêt attaqué est annulé et la cause est renvoyée à la Chambre pénale de recours de la Cour de justice de la République et canton de Genève pour nouvelle décision dans le sens des considérants.
2.
Une indemnité de dépens de 1'500 francs est allouée à l'avocat du recourant, pour la procédure fédérale, à la charge de la République et canton de Genève.
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 Cour de justice de la République et canton de Genève, Chambre pénale de recours.
Lausanne, le 9 février 2017
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président : Merkli
La Greffière : Sidi-Ali