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 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. Ce dernier avait remis à Y._ deux avis de droit, qui mentionnaient que la dénonciation pénale du cadre solliciteur devait s'imposer. Y._, titulaire d'un brevet d'avocat, n'avait pas dénoncé le cadre aux autorités pénales. 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. B. Le 9 juillet 2014, le ministère public a prévenu Y._ d'entrave à l'action pénale (art. 305 CP) pour s'être abstenu, en sa qualité de directeur du domaine " Droit et risques " à la direction générale 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 ledit cadre en avait été retardée. C. Par ordonnance de classement partiel rendue le 31 juillet 2015, le ministère public a classé la procédure pénale à l'égard de Y._, refusé de lui allouer une indemnité ou un montant à titre de réparation du tort moral et l'a condamné, conjointement et solidairement avec X._, 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 Y._. 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 23'059 fr. et une indemnité pour ses frais de défense dans le cadre de la procédure de recours par 1200 francs. Subsidiairement, il prend les mêmes conclusions et requiert le renvoi de la cause à l'autorité cantonale pour qu'elle statue dans le sens des considérants. 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. Le recourant s'est déterminé sur celles-ci.