Faits : A. Par ordonnance du 5 février 2015, le Ministère public genevois a ordonné le classement de la procédure ouverte à l'encontre de X._. Il lui a alloué les montants de 739 fr. à titre d'indemnité pour perte de gain et de 11'320 fr. (99 jours à 30 fr. + 5 jours à 150 fr. + 76 jours à 100 fr.) à titre de réparation du tort moral subi en raison d'une atteinte particulièrement grave à sa personnalité. B. Par arrêt du 10 juillet 2015, la Chambre pénale de recours de la Cour de justice genevoise a partiellement admis le recours de X._ et annulé l'ordonnance entreprise en tant qu'elle n'allouait pas au recourant d'indemnité pour ses frais de séjour en Suisse et ses frais de déplacement aux audiences, et qu'elle n'assortissait pas d'intérêts les montants devant être accordés. Au titre de son dommage économique, elle a alloué à X._ la somme de 852 fr. 80 avec intérêts à 5% dès le 9 juillet 2014 pour son entretien durant son séjour en Suisse du 18 juin au 31 juillet 2014 et les sommes de 699 euros 95 avec intérêts à 5% dès le 20 septembre 2014 et 495 euros avec intérêts à 5% dès le 18 novembre 2014 pour ses frais de déplacement aux audiences des 29 septembre et 20 novembre 2014. Elle lui a également alloué la somme de 11'320 fr. avec intérêts à 5% dès le 1 er mars 2014 pour le tort moral subi en raison de la détention injustifiée. Le montant de 739 fr. accordé par le Ministère public à titre d'indemnité pour perte de gain lui demeurait acquis pour le surplus. Les faits retenus par la cour cantonale à l'appui de son arrêt sont les suivants. X._ a été condamné le 26 septembre 2013, pour infraction à la LStup, à une peine privative de liberté de 3 ans, avec sursis partiel à concurrence de 21 mois, sous déduction de 368 jours de détention provisoire. Le 28 novembre 2013, une altercation est survenue entre plusieurs détenus dans les cuisines de la prison de A._, où X._ était employé depuis le 31 janvier 2013. L'un des détenus a été poignardé; il a désigné plusieurs détenus albanais, dont X._, comme étant les auteurs. X._, qui devait être libéré le 23 décembre 2013, a été immédiatement sanctionné par la Direction de la prison d'une suppression de son emploi en cuisine et d'un placement en cellule forte d'une durée de cinq jours. Il a ensuite fait l'objet d'une mesure d'isolement afin d'éviter tout risque de collusion. Le 29 novembre 2013, une instruction pénale a été ouverte, dans le cadre de laquelle X._ a été prévenu, le 6 décembre 2013, de complicité de tentative de meurtre, subsidiairement de complicité de lésions corporelles graves. Sur ordre du Ministère public, l'intéressé a subi une fouille corporelle complète et divers prélèvements (frottis sous-unguéaux, sang, urine) ont été effectués pour analyse. L'altercation a par ailleurs fait l'objet d'un article dans un quotidien genevois en décembre 2013, relatant l'ouverture d'une procédure pour tentative de meurtre impliquant trois prisonniers d'origine balkanique détenus à la prison de A._ pour d'autres affaires. Au terme de son audition par le Ministère public le 6 décembre 2013, X._ a été placé en détention provisoire, ce qui a eu pour effet d'interrompre l'exécution de la peine qu'il purgeait. Par ordonnance du 8 décembre 2013, le Tribunal des mesures de contrainte (TMC) a confirmé sa mise en détention provisoire pour une durée de trois mois, puis, ultérieurement, la prolongation de celle-ci. A la requête de l'intéressé, la levée avec effet immédiat de la mesure d'isolement dont il faisait l'objet a été ordonnée par le Ministère public le 19 février 2014. Le 27 mai 2014, le TMC a ordonné la mise en liberté de X._, moyennant diverses mesures de substitution, comprenant l'obligation de résider à Genève, une interdiction de quitter le territoire suisse, le dépôt de son passeport et d'une garantie de 10'000 fr. et l'obligation de se présenter deux fois par semaine à un poste de police ainsi que de donner suite à toute convocation par la police ou le Ministère public. X._ est toutefois demeuré incarcéré à la prison de A._ jusqu'au 18 juin 2014, en raison du solde de peine qu'il devait encore exécuter. Le 29 juillet 2014, le Ministère public a allégé les mesures de substitution imposées à X._, ce dernier n'ayant plus à résider à Genève ni à se présenter deux fois par semaine au poste de police. Son passeport lui a été restitué le 31 juillet 2014 et il a regagné l'Albanie. Le recourant a été convoqué à des audiences du Ministère public les 29 septembre et 20 novembre 2014. C. Contre ce dernier arrêt, X._ dépose un recours en matière pénale devant le Tribunal fédéral. Il conclut, avec suite de frais et dépens, à l'annulation de l'arrêt attaqué et à sa réforme en ce sens que l'autorité cantonale lui octroie les sommes de 1'312 fr. 55 avec intérêts à 5% dès le 1 er juillet 2014, 1'741 fr. 55 avec intérêts à 5% dès le 1 er août 2014, 73 fr. 50 avec intérêts à 5% dès le 20 octobre 2014 et 1'197 euros 95 avec intérêts à 5% dès le 20 octobre 2014 à titre d'indemnité pour son dommage économique, ainsi qu'une indemnité pour son tort moral découlant de la détention injustifiée à hauteur de 36'000 fr. avec intérêts à 5% l'an dès le 1 er mars 2014. A titre subsidiaire, il demande l'annulation de l'arrêt attaqué et le renvoi de la cause à l'autorité cantonale pour nouvelle décision. En outre, il sollicite l'assistance judiciaire. D. Invités à se déterminer, la cour cantonale s'est référée à son arrêt et le Ministère public a conclu au rejet du recours.