Faits : A. En mai 2010, un cadre de A._ aurait sollicité d'un tiers, peu avant la passation d'un contrat entre l'entreprise de celui-ci et A._, un avantage indu, soit le versement de 100'000 francs. Un autre tiers (ci-après le témoin) a assisté à cette scène. X._, directeur général de A._ jusqu'au 12 septembre 2013, avait été informé d'un comportement potentiellement répréhensible du cadre précité et avait constitué un dossier confidentiel à l'automne 2010. Selon une note du 18 octobre 2010, il s'était entretenu avec le tiers précité et lui avait demandé une confirmation écrite, laquelle avait été établie le 3 décembre 2010. Selon une note du 20 octobre 2010, le témoin présent lors de la sollicitation craignait une plainte en diffamation et estimait que sa position de mandataire du tiers précité amenuiserait la portée de sa corroboration. X._ avait demandé au directeur chargé du domaine " Droit et risques " à A._, Y._, de prendre conseil auprès d'un avocat. Il n'avait pas lu les avis de droit demandés, mais en avait discuté avec Y._. Dans une note du 12 janvier 2011, X._ aurait mentionné une " obligation de dénoncer ". Début 2011, il a augmenté le salaire du cadre précité et lui a octroyé un salaire rétroactif. Ce cadre a ensuite été détaché auprès d'une structure partenaire jusqu'à création d'une nouvelle entité qui l'a engagé formellement dès le 1er janvier 2012. Le 5 mai 2014, la Cour des comptes de la République et canton de Genève a dénoncé au Ministère public de la République et canton de Genève les soupçons de corruption passive (art. 322quater CP) qui lui étaient apparus lors d'un audit conduit au sein de A._. Le 5 juin 2014, A._ a déposé plainte pénale contre le cadre soupçonné de corruption, relevant qu'il ne s'expliquait pas le silence de X._. B. Le 9 juillet 2014, le ministère public a prévenu X._ d'entrave à l'action pénale (art. 305 CP) pour s'être abstenu, en sa qualité de directeur général de A._, de dénoncer, entre 2010 et 2014, le comportement suspect de corruption du cadre précité, contrairement à ce que lui imposait l'art. 33 de la loi genevoise d'application du code pénal suisse et d'autres lois fédérales en matière pénale, entrée en vigueur le 1er janvier 2011 (LaCP/GE; RS/GE E 4 10). En vertu de cette dispo sition, toute autorité, tout membre d'une autorité, tout fonctionnaire au sens de l'article 110 al. 3 CP et tout officier public acquérant, dans l'exercice de ses fonctions, connaissance d'un crime ou d'un délit poursuivi d'office est tenu d'en aviser sur-le-champ la police ou le ministère public (art. 302 al. 2 CPP). Le ministère public a estimé que l'ouverture d'une procédure pénale contre le cadre en avait été retardée. Dans la mesure où ce cadre avait été promu, l'extension de l'instruction à la gestion déloyale des intérêts publics (art. 314 CP) était réservée. C. Par ordonnance de classement partiel du 31 juillet 2015, le ministère public a classé la procédure pénale à l'égard de X._, a refusé de lui allouer une indemnité ou un montant à titre de réparation du tort moral et l'a condamné, conjointement et solidairement avec Y._, aux frais de la procédure par 2'500 francs. La procédure pénale suivait sa voie pour le surplus, soit notamment en ce qui concerne l'accusation de corruption passive portée contre le cadre précité. D. Par arrêt du 14 octobre 2015, la Chambre pénale de recours de la Cour de justice de la République et canton de Genève a rejeté le recours formé contre cette ordonnance par X._. E. Ce dernier forme un recours en matière pénale auprès du Tribunal fédéral contre cet arrêt. Il conclut, avec suite de frais et dépens, à son annulation et à l'annulation de l'ordonnance du 31 juillet 2015 en tant qu'elle lui refuse une indemnité pour ses frais de défense et le condamne aux frais de la procédure. Il sollicite qu'il lui soit octroyé, à charge de l'Etat de Genève, une indemnité pour ses frais de défense durant la procédure d'instruction par 24'958 fr. 10 à laquelle s'ajouteront les frais de photocopies payés à l'Etat de Genève par 309 fr. et une indemnité pour ses frais de défense dans le cadre de la procédure de recours par 1000 francs. Subsidiairement, il requiert l'annulation de l'arrêt du 14 octobre 2015 et de l'ordonnance du 31 juillet 2015, en tant qu'elle lui refuse une indemnité pour ses frais de défense et le condamne aux frais de la procédure, et le renvoi de la cause à l'autorité précédente pour nouvelle décision. Invités à se déterminer sur le recours, l'autorité précédente s'est référée à son arrêt sans formuler d'observations, le ministère public a conclu au rejet du recours.