Faits :
A.
Par ordonnance du 15 octobre 2014, le Ministère public du canton de Genève a classé la procédure pénale ouverte à l'encontre de X._ pour infraction à la Loi fédérale sur les stupéfiants (<ref-law>) et infraction à la Loi fédérale sur les étrangers (art. 115 LEtr). Il a rejeté les prétentions en indemnité de X._ fondées sur les art. 429 al. 1 let. a et c CPP et a mis les frais de la procédure, d'un montant de 350 fr., à la charge de celui-ci.
B.
Par arrêt du 3 mars 2015, la Chambre pénale de recours de la Cour de justice a rejeté le recours de X._ à l'encontre du refus d'indemnisation décidé dans l'ordonnance du 15 octobre 2014 du Ministère public.
C.
Par arrêt du 5 février 2016 (6B_396/2015), le Tribunal fédéral a annulé la décision du 3 mars 2015 et renvoyé la cause à la Chambre pénale de recours pour qu'elle se saisisse des griefs soulevés sur l'application de l'<ref-law> et rende une nouvelle décision.
D.
Statuant sur renvoi le 16 mars 2016, la Chambre pénale de recours a partiellement admis le recours de X._ contre l'ordonnance du 15 octobre 2014. Elle a laissé les frais de la procédure préliminaire à la charge de l'Etat et alloué à X._ une indemnité de 6'048 fr. TTC pour ses frais de défense en procédure préliminaire. Elle a mis à la charge de X._ le quart des frais de la procédure de recours, comprenant un émolument de 1'000 fr., et lui a alloué une indemnité de défense de 1'000 fr. TTC pour la procédure de recours. Enfin, elle a compensé la charge des frais de la procédure de recours avec l'indemnité de défense accordée pour celle-ci.
E.
X._ forme un recours en matière pénale au Tribunal fédéral contre cet arrêt. Il conclut à l'annulation de l'arrêt attaqué et à sa réforme en ce sens que les frais sont intégralement laissés à la charge de l'Etat et qu'une indemnité de procédure de 1'836 fr. TTC lui est allouée pour la procédure de recours cantonale. Il sollicite par ailleurs l'assistance judiciaire.
F.
Invités à se déterminer sur le recours, la cour cantonale et le ministère public ont renoncé à présenter des observations, ce dernier concluant au rejet du recours avec suite de frais.

Considérant en droit :
1.
Invoquant une violation de l'<ref-law>, le recourant reproche à la cour cantonale d'avoir mis à sa charge un quart des frais de la procédure de recours.
1.1. Selon l'art. 428 al. 1, 1ère phrase, CPP, les frais de la procédure de recours sont mis à la charge des parties dans la mesure où elles ont obtenu gain de cause ou succombé. L'<ref-law> régit les cas dans lesquels les frais de la procédure sont mis à la charge de la partie recourante qui obtient une décision qui lui est plus favorable.
Pour déterminer si une partie succombe ou obtient gain de cause, il faut examiner dans quelle mesure ses conclusions sont admises en deuxième instance (arrêts 6B_1025/2014 du 9 février 2015 consid. 2.4.1; 6B_1046/2013 du 14 mai 2014 consid. 3.3; 6B_586/2013 du 1er mai 2014 consid. 3.2; 6B_438/2013 du 18 juillet 2013 consid. 2.4).
1.2. Le 30 janvier 2014, le recourant a formulé auprès du ministère public une demande d'indemnisation pour ses frais de défense pour la procédure préliminaire. Il concluait à l'octroi d'une indemnité de 5'842 fr. 80 TTC sur la base d'un relevé d'activité de 20 heures et 10 minutes (arrêt attaqué, consid. B. e p. 3). Le recourant a repris cette conclusion dans son acte de recours cantonal (arrêt attaqué, consid. A. a p. 2). Après avoir examiné le relevé d'activité produit, la cour cantonale a arrêté à 14 le nombre raisonnable d'heures à indemniser, au tarif horaire moyen de 400 fr. résultant de la mise en oeuvre tant d'un avocat stagiaire que d'un avocat breveté. Le montant de l'indemnité s'élevait ainsi à 5'600 fr., soit 6'048 fr. en ajoutant la TVA (arrêt attaqué, consid. 6 p. 6-7).
La cour cantonale a mis à la charge du recourant un quart des frais de la procédure de recours. Elle a considéré que le recourant avait eu gain de cause, mais pas intégralement, sur la question de l'indemnisation de son défenseur, dans la mesure où il obtenait " grosso modo trois quarts du montant réclamé " (arrêt attaqué, consid. 7 p. 7).
1.3. Comme le relève le recourant, la cour cantonale lui a ainsi accordé une indemnité pour ses frais de défense en procédure préliminaire d'un montant supérieur (6'048 fr. TTC) à celui auquel il avait conclu (5'842 fr. 80 TTC), bien qu'elle ait retranché 6 heures et 10 minutes du relevé d'activité produit. Ce résultat s'explique par le tarif horaire appliqué par l'autorité précédente, à savoir un tarif moyen de 400 fr. par heure, alors qu'à teneur du relevé d'activité du recourant, la plupart des heures effectuées étaient facturées à 250 fr. de l'heure, correspondant à l'activité de l'avocat stagiaire. La cour cantonale a ainsi appliqué un tarif horaire moyen supérieur à celui allégué par le recourant.
Quoi qu'il en soit, les motifs qui ont conduit à ce résultat sont sans portée; il est déterminant, en revanche, que le recourant se soit vu allouer un montant légèrement supérieur à celui auquel il avait conclu, d'où il découle que ses conclusions relatives à l'indemnisation de ses frais de défense pour la procédure préliminaire ont été entièrement admises (supra consid. 1.1 in fine). Partant, c'est en violation du droit fédéral que la cour cantonale a considéré que le recourant n'avait pas intégralement obtenu gain de cause, ce qui justifiait de mettre un quart des frais de la procédure de recours à sa charge (<ref-law>). Pour le surplus, il n'apparaît pas que les conditions de l'<ref-law>, qui permettent de mettre les frais à la charge d'une partie qui a obtenu une décision plus favorable, soient réalisées en l'espèce. Le recours doit donc être admis en tant que l'arrêt cantonal met un quart des frais de la procédure de recours à la charge du recourant.
2.
Le recourant se plaint d'une violation de l'<ref-law>, d'un établissement manifestement inexact des faits pertinents (art. 97 et 105 al. 2 LTF), ainsi que d'une violation de son droit d'être entendu (art. 29 al. 2 Cst.) en relation avec l'allocation d'une indemnité de 1'000 fr. TTC pour ses frais de défense en instance de recours.
2.1. Selon l'<ref-law>, applicable à la procédure d'appel par le renvoi de l'<ref-law>, le prévenu acquitté totalement ou en partie ou au bénéfice d'un classement a droit à une indemnité notamment pour ses dépenses occasionnées par l'exercice raisonnable de ses droits de procédure (let. a). L'art 429 al. 2 prévoit que l'autorité pénale examine d'office les prétentions du prévenu. Elle peut enjoindre à celui-ci de les chiffrer et de les justifier. La jurisprudence a déduit de cette dernière disposition qu'il incombe à l'autorité pénale, à tout le moins, d'interpeller le prévenu sur la question de l'indemnité et de l'enjoindre au besoin de chiffrer et justifier ses prétentions en indemnisation (<ref-ruling> consid. 1.3.1 p. 240). L'<ref-law> spécifie pour la procédure de recours que si ni un acquittement total ou partiel, ni un classement de la procédure ne sont prononcés mais que le prévenu obtient gain de cause sur d'autres points, il a droit à une juste indemnité pour ses dépenses.
Savoir si le recours à un avocat procède d'un exercice raisonnable des droits de procédure et si, par conséquent, une indemnité pour les frais de défense selon l'<ref-law> peut être allouée au prévenu, est une question de droit fédéral que le Tribunal fédéral revoit librement (<ref-ruling> consid. 3.2.1 p. 169). Il n'en va pas différemment en ce qui concerne l'<ref-law>, qui reprend la même notion de dépenses occasionnées par l'exercice raisonnable de ses droits de procédure. C'est en premier lieu aux autorités pénales qu'il appartient d'apprécier le caractère raisonnable de l'activité de l'avocat et elles disposent dans ce cadre d'un pouvoir d'appréciation considérable. Le Tribunal fédéral s'impose par conséquent une certaine retenue lors de l'examen de l'évaluation faite par l'autorité précédente; il n'intervient que lorsque celle-ci a clairement excédé son pouvoir d'appréciation et que les honoraires alloués sont hors de toute proportion raisonnable avec les prestations fournies par l'avocat (<ref-ruling> consid. 3.2.1 p. 169).
Selon la jurisprudence rendue en matière de dépens, la garantie du droit d'être entendu implique que lorsque le juge statue sur la base d'une liste de frais, il doit, s'il entend s'en écarter, au moins brièvement indiquer les raisons pour lesquelles il tient certaines prétentions pour injustifiées, afin que son destinataire puisse attaquer la décision en connaissance de cause (cf. arrêts 6B_833/2015 du 30 août 2015 consid. 2.3; 6B_124/2012 du 22 juin 2012 consid. 2.2 et les références citées).
2.2. Le recourant a sollicité une indemnité pour ses frais de défense en instance de recours à hauteur de 1'836 fr. TTC (arrêt attaqué, consid. D. a. p. 3).
La cour cantonale a considéré que la demande d'indemnité n'était pas explicitée. Le recours et la réplique n'avaient pas été signés par l'avocat directement mandaté par le recourant. Dans ces circonstances, une indemnité de 1'000 fr. TTC apparaissait équitable, au sens de l'<ref-law>P.
2.2.1. En réponse au reproche de n'avoir pas explicité ses prétentions en indemnisation, le recourant fait valoir que dans son acte de recours cantonal, il avait justifié le montant réclamé - lequel n'incluait d'ailleurs pas la réplique rédigée ultérieurement - de la façon suivante: " Le présent recours a provoqué l'activité suivante pour le recourant: 5 heures d'activité d'avocat-stagiaire à CHF 250.-/heure et 1 heure d'activité d'avocat chef d'étude à CHF 450.-/heure, soit un montant total de CHF 1'836.- TTC [...] " (recours cantonal du 27 octobre 2014, n° 69 p. 10-11). Ce faisant, le recourant a décrit l'activité déployée par son conseil pour la procédure de recours cantonale et expliqué comment il parvenait à un montant total de 1'836 francs. Ces éléments sont pertinents et doivent par conséquent être ajoutés à l'état de fait (<ref-law>).
Même dans l'hypothèse où le recourant n'aurait pas suffisamment chiffré et justifié ses prétentions pour que la cour cantonale entre en matière, il incombait alors à celle-ci de l'interpeller à cet égard (cf. <ref-law> par renvoi de l'<ref-law>). L'autorité précédente n'indique pas l'avoir fait, ni que le recourant aurait omis de fournir les renseignements demandés.
2.2.2. Le recours cantonal contient, en bas de la dernière page, la mention dactylographiée " Pour le recourant, Romain Jordan " avec les lettres manuscrites " Exct " ajoutées devant le nom de l'avocat et une signature manuscrite en dessous dudit nom (recours cantonal du 27 octobre 2014 p. 11). La cour cantonale ne dit pas en quoi ces éléments justifieraient de s'écarter de la demande d'indemnisation formulée. On ne saurait, en tous les cas, en déduire que le conseil du recourant n'a pas fourni l'activité qu'il allègue.
2.2.3. Au vu de ce qui précède, les motifs invoqués par la cour cantonale pour ne pas entrer en matière sur le décompte d'activité produit par le recourant et, partant, fixer une indemnité en équité, se fondent sur un état de fait incomplet, respectivement sont sans pertinence sous l'angle de l'<ref-law>. Dans la mesure où la cour cantonale dispose d'un large pouvoir d'appréciation en ce qui concerne l'examen du caractère raisonnable de l'activité de l'avocat, il convient de lui renvoyer la cause pour qu'elle statue à nouveau sur l'indemnisation des frais de défense en instance de recours en se fondant sur l'état de fait complété selon ce qui précède, après avoir, si elle l'estime nécessaire, requis du recourant qu'il produise un relevé détaillé des opérations de son conseil.
Compte tenu de ce qui précède, il n'y a pas lieu d'examiner le grief de violation du droit d'être entendu soulevé par le recourant.
3.
Le recours est admis et la cause renvoyée à la cour cantonale pour qu'elle rende une nouvelle décision sur la répartition des frais de la procédure de recours ainsi que sur l'indemnisation des frais de défense du recourant pour la procédure de recours. Le canton de Genève sera dispensé des frais (<ref-law>). Il versera en revanche au recourant une indemnité de dépens pour la procédure devant le Tribunal fédéral (<ref-law>). La requête d'assistance judiciaire devient ainsi sans objet.

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis, le jugement attaqué annulé et la cause renvoyée à l'autorité cantonale pour nouvelle décision.
2.
Il n'est pas perçu de frais judiciaires.
3.
Le canton de Genève versera en mains du conseil du recourant une indemnité de 3000 fr. à titre de dépens.
4.
Le présent arrêt est communiqué aux parties et à la Cour de justice de la République et canton de Genève, Chambre pénale de recours.
Lausanne, le 22 mars 2017
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
La Greffière : Musy