Faits :
A.
Dans le cadre d'une procédure pénale ouverte à l'encontre de X._, le Ministère public de la République et canton de Genève a rendu une ordonnance de non-entrée en matière le 5 novembre 2015 dans laquelle il refuse d'allouer à ce dernier une indemnité pour ses frais d'avocat et pour la privation de liberté subie.
B.
Statuant par arrêt du 17 mars 2016 sur le recours formé par X._ contre l'ordonnance précitée, la Chambre pénale de recours de la République et du canton de Genève l'a rejeté.
En bref, il en ressort les faits suivants.
Le 30 mai 2015 (cf. <ref-law>), à 10h, X._, ressortissant turc domicilié en Turquie, a été appréhendé par les gardes-frontière lors de son entrée en Suisse, au passage frontière de Ferney-Voltaire, au volant d'un véhicule immatriculé à Genève et dont la détentrice est A._. Lors du contrôle de son permis de conduire, les gardes-frontière ont constaté qu'il s'agissait d'une contrefaçon d'un permis de conduire turc.
A 10h37, à la suite d'un contrôle positif à la cocaïne, les agents ont fait appel à la brigade canine. La fouille corporelle s'est révélée négative. Ils ont ensuite, à 13h30, demandé l'envoi d'une patrouille.
A 13h55, X._ a été remis à une patrouille de gendarmerie pour la suite de la procédure et le ministère public a été avisé de l'arrestation provisoire à 14h48.
X._ a été auditionné par les gendarmes de 15h28 à 17h04. Il a été libéré à 17h25 et son permis de conduire transmis à la Brigade de police technique et scientifique (ci-après: BPTS) pour analyse.
Le 11 juin 2015, X._ a retourné au bureau de police, visiblement par l'intermédiaire de A._, le formulaire relatif à sa situation personnelle et divers documents.
A teneur du rapport du 12 août 2015 de la BPTS, le permis de conduire de X._ ne présentait aucun signe de falsification et les autorités turques avaient confirmé avoir émis ledit document. Le 15 juin 2015, X._ avait déclaré avoir perdu son permis de conduire et avait obtenu la délivrance d'un nouveau document.
Par ordonnance « fichet » du 14 septembre 2015, le ministère public a décidé de ne pas entrer en matière sur les faits, en application de l'<ref-law>, avec la mention « pas d'infraction ».
C.
X._ forme un recours en matière pénale au Tribunal fédéral contre l'arrêt du 17 mars 2016 et conclut, avec suite de dépens, à l'allocation en sa faveur d'une indemnité équitable de 500 fr. pour la privation de liberté subie et d'une indemnité de 2'600 fr. pour les frais d'avocat encourus pour la procédure cantonale. Il sollicite par ailleurs l'assistance judiciaire et la désignation de son conseil en qualité d'avocat d'office.
Invitée à se déterminer sur le recours, la cour cantonale, se référant aux considérants de son arrêt, y a renoncé. Le ministère public a conclu au rejet. Le recourant a répliqué.

Considérant en droit :
1.
Le recours en matière pénale au Tribunal fédéral est ouvert contre la décision fixant l'indemnisation prévue à l'<ref-law> (<ref-ruling> consid. 1 p. 208).
2.
En vertu de l'<ref-law>, si le prévenu est acquitté totalement ou en partie ou s'il bénéficie d'une ordonnance de classement, il a droit à une indemnité pour les dépenses occasionnées par l'exercice raisonnable de ses droits de procédure (let. a), à une indemnité pour le dommage économique subi au titre de sa participation obligatoire à la procédure pénale (let. b) et à une réparation du tort moral subi en raison d'une atteinte particulièrement grave à sa personnalité, notamment en cas de privation de liberté (let. c). 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 (<ref-law>).
L'<ref-law> fonde un droit à des dommages et intérêts et à une réparation du tort moral résultant d'une responsabilité causale de l'Etat. La responsabilité est encourue même si aucune faute n'est imputable aux autorités (arrêt 6B_928/2014 du 10 mars 2016 consid. 2 non publié in <ref-ruling>). L'Etat doit réparer la totalité du dommage qui présente un lien de causalité avec la procédure pénale au sens du droit de la responsabilité civile (Message du 21 décembre 2005 relatif à l'unification du droit de la procédure pénale, FF 20061313 ch. 2.10.3.1; ci-après Message CPP).
3.
Le recourant, qui se réfère aux art. 215, 217 et 429 al. 1 let. c CPP, conteste le refus de l'autorité précédente de lui allouer une indemnité pour le tort moral qu'il allègue avoir subi en raison d'atteintes particulièrement graves à sa personnalité.
3.1. Afin d'avoir droit à l'indemnité visée par l'art. 429 al. 1 let. c CPP, l'intensité de l'atteinte à la personnalité doit être analogue à celle requise dans le contexte de l'<ref-law> (arrêts 6B_928/2014 précité consid. 5.1, non publié in <ref-ruling>).
L'indemnité pour tort moral sera régulièrement allouée si le prévenu s'est trouvé en détention provisoire ou en détention pour des motifs de sûreté. Outre la détention, peut constituer une grave atteinte à la personnalité, par exemple, une arrestation ou une perquisition menée en public ou avec un fort retentissement médiatique, une durée très longue de la procédure ou une importante exposition dans les médias, ainsi que les conséquences familiales, professionnelles ou politiques d'une procédure pénale, de même que les assertions attentatoires aux droits de la personnalité qui pourraient être diffusées par les autorités pénales en cours d'enquête. En revanche, il n'y a pas lieu de prendre en compte les désagréments inhérents à toute poursuite pénale comme la charge psychique que celle-ci est censée entraîner normalement chez une personne mise en cause (arrêt 6B_928/2014 précité consid. 5.1 et les références citées).
L'ampleur de la réparation morale dépend avant tout de la gravité des souffrances physiques ou psychiques consécutives à l'atteinte subie par l'intéressé et de la possibilité d'adoucir sensiblement, par le versement d'une somme d'argent, la douleur morale qui en résulte. Sa détermination relève du pouvoir d'appréciation du juge. En raison de sa nature, l'indemnité pour tort moral, qui est destinée à réparer un dommage qui ne peut que difficilement être réduit à une simple somme d'argent, échappe à toute fixation selon des critères mathématiques, de sorte que son évaluation en chiffres ne saurait excéder certaines limites. L'indemnité allouée doit toutefois être équitable (<ref-ruling> consid. 5.1 p. 704 s.; cf. également <ref-ruling> consid. 11.2 p. 98).
Selon la jurisprudence, un montant de 200 fr. par jour en cas de détention injustifiée de courte durée constitue une indemnité appropriée, dans la mesure où il n'existe pas de circonstances particulières qui pourraient fonder le versement d'un montant inférieur ou supérieur (arrêt 6B_909/2015 du 22 juin 2016 consid. 2.2.1). Le taux journalier n'est qu'un critère qui permet de déterminer un ordre de grandeur pour le tort moral. Il convient ensuite de corriger ce montant compte tenu des particularités du cas (durée de la détention, retentissement de la procédure sur l'environnement de la personne acquittée, gravité des faits reprochés, etc.). Lorsque la détention injustifiée s'étend sur une longue période, une augmentation linéaire du montant accordé dans les cas de détention plus courte n'est pas adaptée, car le fait de l'arrestation et de la détention pèse d'un poids en tout cas aussi important que l'élément de durée pour apprécier l'atteinte que subit la personne incarcérée. Aussi, lorsque la durée de détention est de plusieurs mois, convient-il en règle générale de réduire le montant journalier de l'indemnité (arrêt 6B_909/2015 précité consid. 2.2.1; cf. <ref-ruling> consid. 3b p. 156).
La fixation de l'indemnité pour tort moral est une question d'application du droit fédéral, que le Tribunal fédéral examine donc librement. Dans la mesure où celle-ci relève pour une part importante de l'appréciation des circonstances, il intervient avec retenue. Il le fait notamment si l'autorité cantonale a mésusé de son pouvoir d'appréciation, en se fondant sur des considérations étrangères à la disposition applicable, en omettant de tenir compte d'éléments pertinents ou encore en fixant une indemnité inéquitable parce que manifestement trop faible ou trop élevée (<ref-ruling> consid. 6.3.1 p. 344 et la référence citée).
3.2. La notion de privation de liberté au sens de l'art. 429 al. 1 let. c CPP doit s'interpréter à la lumière des art. 51 et 110 al. 7 CP. Selon cette dernière disposition, est considérée comme détention avant jugement, toute détention ordonnée au cours d'un procès pénal pour les besoins de l'instruction, pour des motifs de sûreté ou en vue de l'extradition.
Selon la jurisprudence rendue avant l'entrée en vigueur du CPP, qui examinait cette question sous l'angle du droit constitutionnel et conventionnel, le fait de retenir une personne pendant une durée de quatre à six heures ne constituait pas une violation de la liberté personnelle (<ref-ruling> consid. 3 p. 152; <ref-ruling> consid. 4a p. 140; <ref-ruling> consid. 1 p. 180). Dans un arrêt publié aux <ref-ruling> (consid. 4 p. 273), le Tribunal fédéral a précisé que la détention préventive devait être imputée de la peine indépendamment de savoir quelle autorité (policier ou magistrat) l'avait ordonnée.
La doctrine, quant à elle, considère comme une détention avant jugement au sens de l'<ref-law> toute privation de liberté d'une durée supérieure à trois heures (YVAN JEANNERET, in Commentaire romand, Code pénal I, 2009, no 1 ad <ref-law> et les références citées; METTLER/SPICHTIN, in Basler Kommentar, Strafrecht I, 3e éd. 2013, nos 13 et 17 ad <ref-law> et no 3 ad <ref-law> et les références citées). Elle fonde notamment cette limite sur le système mis en place par les <ref-law> (cf. YVAN JEANNERET, op. cit., no 3 ad. <ref-law>).
Selon le message du Conseil fédéral, lors d'une appréhension (parfois aussi appelée contrôle d'identité), la police restreint passagèrement la liberté de mouvement de personnes dans l'exercice de son droit d'investigation. Elle permet à la police de conduire une personne appréhendée au poste. Elle se distingue de l'arrestation des <ref-law> en ce sens que l'arrestation présuppose que la personne visée soit soupçonnée de manière concrète d'avoir commis une infraction, alors que l'appréhension doit permettre de définir le cercle des personnes soupçonnées. Le séjour au poste d'une personne appréhendée doit (précisément parce qu'il n'existe contre elle aucun soupçon concret) durer nettement moins de trois heures au total (Message CPP p. 1205 s. ch. 2.5.3.2). L'appréhension ne doit pas être considérée comme une détention avant jugement et ne donne en principe pas droit à une indemnisation au sens de l'<ref-law>, à condition toutefois que la durée de la mesure de contrainte, à l'exclusion de l'interrogatoire formel, ne dépasse pas trois heures (ULRICH WEDER, in Kommentar zur Schweizerischen Strafprozessordnung, Donatsch/Hansjakob/Lieber [éd.], 2e éd. 2014, no 30 ad <ref-law>; dans ce sens également NIKLAUS SCHMID, Schweizerische Strafprozessordnung, Praxiskommentar, 2e éd. 2013, no 12 ad <ref-law>). L'arrestation quant à elle est une mesure privative de liberté (Message CPP p. 1207 ch. 2.5.3.3). En application de l'<ref-law>, la prolongation de l'arrestation doit être ordonnée par un membre du corps de police habilité par la Confédération ou le canton si la personne arrêtée n'est prévenue que d'une contravention et si l'arrestation dure plus de trois heures. Le législateur a ainsi considéré qu'une durée de trois heures constituait une limite au-delà de laquelle l'atteinte à la liberté était plus grave (arrêt 6B_53/2013 du 8 juillet 2013 consid. 2.2). Il s'ensuit qu'une appréhension, suivie d'une arrestation, qui s'étendent sur une durée totalisant plus de trois heures, constituent une atteinte à la liberté qui peut donner lieu à indemnisation. Il convient toutefois de ne pas tenir compte de la durée d'un éventuel interrogatoire formel dans le décompte des heures, seule étant déterminante la période pendant laquelle la personne est retenue à disposition des autorités (arrêt 6B_53/2013 précité consid. 2.2 et la référence citée).
3.3. La cour cantonale a retenu que le recourant avait été appréhendé par les gardes-frontière, le 30 mai 2015 à 10h, au volant d'un véhicule, dans le but de déterminer si une infraction telle que le faux dans les certificats et à la loi sur les stupéfiants avait été commise et avaient, pour ce faire, notamment requis l'intervention de la brigade canine (art. 215 al. 1 let. d CPP). Cette dernière infraction écartée, ils avaient fait appel à la police, à 13h30, pour la suite de la procédure, considérant que le recourant était en possession d'une contrefaçon d'un permis de conduire turc. Il avait été placé en arrestation provisoire à 14h48. Son audition avait duré de 15h28 à 17h04, soit 1h36. Il s'ensuivait que son arrestation, au sens strict, n'avait pas duré plus de trois heures. De même, si l'on devait considérer que le recourant, sitôt écoulées les trois heures admises pour une appréhension, se trouvait en état d'arrestation, soit dès 13h, cette arrestation « étendue » n'avait pas non plus duré plus de trois heures. Le recourant n'avait, dès lors, pas droit, pour ce motif, à une indemnité pour tort moral.
Pour le reste, la cour cantonale a précisé qu'elle ne voyait pas en quoi son audition et l'examen de ses papiers par les gardes-frontière suisses et les gendarmes, en présence d'un interprète turc, pourraient être une source de traumatisme au-delà du poids psychique inhérent à toute procédure pénale, et le recourant ne l'expliquait d'ailleurs pas. Ce dernier, qui y faisait pour la première fois référence dans son recours, se plaignait de deux fouilles corporelles. Le rapport des garde-frontières indiquait effectivement une telle fouille. Le contrôle positif à la cocaïne avait toutefois justifié cette fouille, ainsi que l'appel à la brigade canine. Le rapport de gendarmerie ne faisait, quant à lui, pas état d'une telle mesure qui ne reposait que sur les seules allégations du recourant. Ainsi, si, à l'évidence, une fouille corporelle était une mesure désagréable, les circonstances liées au constat positif de drogue la justifiaient au sens de l'<ref-law> en raison du soupçon d'infraction à la LStup. La cour cantonale en a conclu que le recourant n'avait nullement subi une atteinte particulièrement grave à sa personnalité. C'était donc à juste titre que le ministère public ne lui avait pas accordé d'indemnité pour tort moral.
3.4. Selon les constatations cantonales, le recourant a été appréhendé par les gardes-frontière à 10h. Il a fait l'objet d'un contrôle à la cocaïne à 10h37, à la suite de quoi les agents ont fait appel à la brigade canine. Il a ensuite subi une fouille corporelle, puis a été remis à une patrouille de gendarmerie à 13h55, pour être relâché à 17h25. Le recourant a été gardé à la disposition des garde-frontières puis des gendarmes de 10h à 17h25. Il a ainsi été atteint dans sa liberté pour les besoins de la procédure pénale durant ce laps de temps, soit pendant une durée totalisant plus de trois heures, ce qui donne lieu à indemnisation, et ce indépendamment à quel titre il a été gardé par les gardes-frontière et les gendarmes. La durée de son interrogatoire - quelle qu'elle soit - n'a pas d'incidence en l'espèce dans la mesure où les trois heures sont de toute façon dépassées. Il incombait dès lors à l'autorité précédente de dédommager le recourant pour la période excédant les trois heures, ce qui correspond à un jour d'indemnité.
Aucune autre des circonstances particulières constituant une grave atteinte à la personnalité (cf. supra consid. 3.1) n'est réalisée. Le recourant a certes fait l'objet d'une fouille corporelle, d'un contrôle à la cocaïne et d'une arrestation, menottes aux mains. Sans autres particularités, ceux-ci ne sont cependant pas de nature à outrepasser le seuil des désagréments inhérents à une poursuite pénale. Quant à la période de détention, elle ne saurait être prise en considération une seconde fois pour fonder une indemnisation du recourant. S'agissant de la seconde fouille corporelle de l'intéressé, complètement nu, la cour cantonale a jugé que sa réalité n'était pas établie et ce dernier ne démontre pas l'arbitraire de cette appréciation. Il ne saurait ainsi être question d'une atteinte objectivement grave à la personnalité pour ce motif. Il en va de même de son permis de conduire qui lui a été confisqué, ce d'autant qu'il a obtenu la délivrance d'un nouveau document le 15 juin 2015. En outre, il ne ressort pas de l'arrêt attaqué que le recourant aurait fait état d'effets concrets que le déroulement de la procédure pénale aurait eus sur sa personne. En particulier, il n'apparaît pas qu'il aurait évoqué des souffrances physiques ou psychiques, ni une quelconque autre atteinte particulièrement grave à ses intérêts personnels attestant d'une souffrance morale suffisamment forte du fait des examens auxquels il a été soumis et de son interrogatoire. Dans ces conditions, l'existence d'une atteinte particulièrement grave à la personnalité résultant de ces actes d'instruction ne saurait être admise.
En définitive, seule la détention justifie une indemnisation à l'exclusion des circonstances en lien avec les actes d'instruction évoqués ci-dessus, qui ne constituent pas un facteur d'aggravation du tort moral subi par le recourant. Le recourant ne fournit aucun élément qui légitimerait de s'écarter du montant habituel de 200 fr. (cf. supra consid. 3.1). C'est donc un tel montant qui doit être alloué au recourant et l'arrêt attaqué sera réformé en conséquence.
4.
Le recourant se plaint d'une violation de l'<ref-law>. Il prétend au paiement de 2'600 fr. pour les « frais de défense encourus pour la procédure cantonale », correspondant à 600 fr. pour les frais d'avocat devant le ministère public et à 2'000 fr. à titre d'indemnité pour la procédure de recours (cf. arrêt cantonal let. A p. 2).
4.1. L'allocation d'une indemnité pour frais de défense selon l'<ref-law> n'est pas limitée aux cas de défense obligatoire visés par l'<ref-law>. Elle peut être accordée dans les cas où le recours à un avocat apparaît tout simplement raisonnable. Il faut garder à l'esprit que le droit pénal matériel et le droit de procédure sont complexes et représentent, pour des personnes qui ne sont pas habituées à procéder, une source de difficultés. Celui qui se défend seul est susceptible d'être moins bien loti. Cela ne dépend pas forcément de la gravité de l'infraction en cause. On ne peut pas partir du principe qu'en matière de contravention, le prévenu doit supporter en général seul ses frais de défense. Autrement dit, dans le cadre de l'examen du caractère raisonnable du recours à un avocat, il doit être tenu compte, outre de la gravité de l'infraction et de la complexité de l'affaire en fait ou en droit, de la durée de la procédure et de son impact sur la vie personnelle et professionnelle du prévenu. Déterminer si l'assistance d'un avocat procède d'un exercice raisonnable des droits de procédure et si, par conséquent, une indemnité pour 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. Il s'impose toutefois une certaine retenue lors de l'examen de l'évaluation faite par l'autorité précédente, particulièrement de la détermination, dans le cas concret, des dépenses qui apparaissent raisonnables (<ref-ruling> consid. 2.1 p. 47 et les références citées).
4.2. La cour cantonale a considéré qu'il était manifeste que la procédure pénale incriminée n'était pas complexe puisqu'elle s'était limitée à un examen par la police scientifique du document litigieux. Le recourant, qui avait chargé son amie de fournir les documents demandés et transmettre les informations concernant le permis de conduire, aurait tout aussi bien pu lui demander de solliciter la restitution du document. De plus, le recourant, qui avait annoncé la perte de son permis aux autorités turques et s'était fait délivrer un nouveau document le 15 juin 2015, soit quinze jours après la saisie, n'avait plus la nécessité de le réclamer. La procédure ne présentait, ainsi, ni complexité ni difficultés particulières. Le recours à un avocat, dont on ignorait l'activité, mis à part le courrier adressé au procureur le 15 octobre 2015, n'apparaissait dès lors pas raisonnablement nécessaire.
4.3. La solution cantonale ne peut être partagée. Comme l'indique la jurisprudence, le droit pénal matériel et le droit de procédure sont complexes et représentent, pour des personnes qui ne sont pas habituées à procéder, une source de difficultés (cf. supra consid. 4.1). En l'occurrence, il était reproché au recourant d'avoir circulé au moyen d'un permis de conduire falsifié, faits passibles, à tout le moins, d'une peine privative de liberté de trois ans au plus ou d'une peine pécuniaire. Certes, le recourant n'a été entendu qu'à une seule reprise. Il a toutefois été privé de sa liberté durant plus de trois heures. Son conseil a annoncé sa constitution par courrier du 15 octobre 2015, date à laquelle le permis de conduire n'avait toujours pas été restitué au recourant; il sollicitait le classement de la procédure, la restitution du permis de conduire à l'intéressé ainsi qu'une indemnité pour la privation de liberté subie le 30 mai 2015 et pour les frais d'avocat encourus. Il ne ressort pas de la procédure que le recourant serait familier du droit pénal suisse en particulier, ce d'autant qu'il est domicilié en Turquie. Il a ainsi été contraint d'organiser sa défense en tout cas pour ce qui est de sa détention qui s'est avérée injustifiée. Il en va de même s'agissant de la procédure de recours contre l'ordonnance de non-entrée en matière qui s'est déroulée devant la cour cantonale. Outre que le recours devait être motivé (<ref-law>), et nécessitait donc des connaissances juridiques, la procédure était fondée puisque la cour cantonale a considéré, à tort, que sa privation de liberté ne donnait lieu à aucune indemnisation (cf. supra consid. 3). Au vu de ce qui précède, il apparaît que la cause présentait des difficultés en droit, en particulier en droit de procédure. Dans ces circonstances, il faut admettre que l'intervention de l'avocat s'inscrit dans l'exercice raisonnable des droits de procédure au sens de l'<ref-law>. Ainsi, en confirmant le refus de toute indemnité fondée sur l'<ref-law>, l'autorité précédente a violé cette disposition. Pour le surplus, le recourant n'explique pas précisément sur quels éléments il se base pour réclamer un montant de 2'600 francs. Le Tribunal fédéral ne peut dès lors vérifier s'il est proportionné, et il appartient, en tout état de cause, à l'autorité précédente de déterminer le montant de l'indemnité en application du large pouvoir d'appréciation dont elle dispose en cette matière (cf. supra consid. 4.1 et l'arrêt 6B_439/2013 du 19 juillet 2013 consid. 2.2 et la référence citée). En conséquence, le recours doit être admis et la cause renvoyée à cette autorité pour qu'elle accorde au recourant une indemnité fondée sur l'<ref-law>, respectivement statue sur les indemnités de première et deuxième instance réclamées.
5.
En conclusion, le recours doit être admis et l'arrêt attaqué partiellement réformé en ce sens qu'une indemnité de 200 fr. est allouée au recourant à titre d'indemnité pour tort moral au sens de l'art. 429 al. 1 let. c CPP; pour le surplus, l'arrêt attaqué est annulé et la cause est renvoyée à l'autorité précédente pour nouvelle décision sur l'indemnité au sens de l'<ref-law>.
Le recourant, qui obtient gain de cause, ne supportera pas de frais. Le canton de Genève n'a pas non plus à en supporter (art. 66 al. 1 et 4 LTF). Le recourant a droit à des dépens à la charge du canton. Cela rend sans objet sa demande d'assistance judiciaire.

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis et l'arrêt attaqué réformé en ce sens qu'une indemnité de 200 fr. est allouée au recourant à titre d'indemnité pour tort moral au sens de l'art. 429 al. 1 let. c CPP; pour le surplus, l'arrêt attaqué est annulé et la cause est renvoyée à l'autorité précédente pour nouvelle décision sur l'indemnité au sens de l'<ref-law>.
2.
Il n'est pas perçu de frais judiciaires.
3.
Le canton de Genève versera au conseil du recourant une indemnité de 3'000 fr. à titre de dépens pour la procédure devant le Tribunal fédéral.
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 8 juin 2017
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
La Greffière : Nasel