Faits : A. A.a. Le 12 mars 2015, X._ Company (ci-après: X._) et Y._ ont déposé une plainte pénale contre A._. En substance, ils accusaient A._ d'avoir indûment perçu, à Genève, sur le compte de la Banque B._ de l'association C._, une société panaméenne dont il est l'un des ayants droit économiques, une commission de 4'500'000 USD, payée en 2008 par D._, après l'obtention auprès de ce dernier du financement que les plaignants recherchaient pour la construction d'un hôpital en Arabie Saoudite. Ils exposaient avoir déposé une plainte pénale contre X, peu auparavant, à Paris, pour des faits susceptibles d'être qualifiés, en droit suisse, de corruption privée, d'abus de confiance et de gestion déloyale. Dans les deux plaintes, A._ est présenté comme un employé salarié de la Banque B._, gestionnaire de leurs comptes. Les plaignants expliquaient qu'en date du 10 juillet 2008, D._ avait accordé à X._ un prêt de 157'500'00 USD, en garantie duquel il avait obtenu que Y._ se portât caution et nantît ses avoirs auprès de la Banque B._ à concurrence de 40'000'000 USD. Le 10 juillet 2008, X._ et D._ signaient aussi un accord prévoyant, notamment, le paiement, par prélèvement sur la libération de la première tranche de l'emprunt, d'une commission de placement ou de garantie (" underwriting fee "), correspondant à 3 % du montant du prêt, à savoir 4'500'000 USD. Un litige étant né après le versement de la deuxième tranche du crédit, D._ résiliait, le 30 juillet 2009, le contrat de prêt et demandait à X._ de le lui rembourser, puis, devant le refus de cette dernière, engageait une procédure d'arbitrage contre Y._, fondée sur le cautionnement auquel il avait souscrit. Dans le cours de l'instance, une enquête journalistique était parue, faisant état de commissions occultes, et notamment d'une commission de 4'500'000 USD versée à l'association C._, dont le " gérant ", A._, était décrit comme un proche de Y._. D._ avait alors produit le contrat qu'elle avait passé le 18 juin 2008 avec l'association C._ et qui promettait à celle-ci une rémunération égale à 3 % de la valeur du financement du projet hospitalier. Pour les plaignants, ce contrat occulte, qui prévoyait une rémunération strictement identique au montant de la commission de placement, rétribuait des prestations fictives. A.b. Par arrêt du 4 mars 2014, la Cour d'appel de Paris a rejeté le recours de X._ contre la sentence arbitrale qui l'a condamnée à rembourser le prêt. Il n'était ni allégué ni établi que A._ eût exercé une fonction de direction ou un travail pour X._, ni que Y._, actionnaire à 95 % et président-directeur général de X._, eût reçu quelque commission que ce soit, directement ou indirectement. Sur le moyen tiré d'un contrat de prêt obtenu par corruption, la cour a retenu que, contrairement à ce que soutenait X._, l'activité d'intermédiaire de A._ n'était nullement occulte, puisque l'intéressé avait participé, aux côtés des dirigeants de D._, aux négociations contractuelles avec elle et qu'il n'était nullement démontré que les commissions de placement ne correspondaient pas à une pratique bancaire. Le 24 juin 2015, la Cour de cassation française a rejeté le pourvoi intenté par X._ contre l'arrêt de la Cour d'appel. A.c. Sans ouvrir d'instruction, le Ministère public genevois a ordonné le séquestre des avoirs de l'association C._ auprès de la Banque B._, ainsi que le dépôt de la documentation bancaire usuelle. Il en ressort que les 4'500'000 USD avaient été crédités le 25 juillet 2008 sur le compte de l'association C._, puis, dès le lendemain, transférés vers d'autres comptes. A.d. Entendu par la police, le chef, à l'époque, de l'équipe " Moyen-Orient " chez la Banque B._ a expliqué que A._ était un apporteur d'affaires avec lequel il travaillait depuis une quinzaine d'années. C'était ce dernier qui avait introduit Y._ à la banque. Il n'avait cependant aucun pouvoir sur les comptes ouverts par celui-ci. Pour recevoir les commissions qui lui seraient versées, il avait ouvert un compte au nom de l'association C._. Les 4'500'000 USD qui y étaient parvenus avaient été payés par une filiale de D._, et non par X._; il n'était pas exclu que l'octroi d'une telle commission eût été décidé à l'insu de Y._. A.e. Entendu par le Procureur genevois en qualité de personne appelée à donner des renseignements, le 19 août 2015, A._ a expliqué avoir introduit Y._ auprès de D._ pour obtenir le financement de la construction de l'hôpital et s'être fait promettre par D._ le versement d'une commission de 3 % sur le compte au nom de l'association C._. Il avait ensuite rétribué deux autres partenaires de l'opération, mais ne savait pas si ces derniers avaient rémunéré d'autres personnes encore. Il n'avait jamais été un employé de la Banque B._ ou de la Banque E._, même si sa carte de visite, à l'en-tête de la Banque B._, le qualifiait de " conseiller senior "; il était en réalité un conseiller externe. S'il avait été salarié de la banque, il n'aurait jamais pu encaisser de commission d'apporteur d'affaires. Il a versé au dossier une copie de l'accord passé à ce sujet le 18 juin 2008. A.f. Interpellé sur commission rogatoire internationale, D._ a confirmé, par lettre de son directeur juridique, avoir passé un contrat d'intermédiation avec A._, joignant une copie de l'accord précité et de l'ordre de paiement, daté du 23 juillet 2008. A.g. Par ordonnance du 29 août 2016, le Ministère public du canton de Genève a classé la plainte pénale contre A._. B. Par arrêt du 1er novembre 2016, la Chambre pénale de recours de la Cour de justice genevoise a déclaré irrecevable le recours formé par Y._ et a admis très partiellement celui formé par X._ sur la question des frais de procédure. C. Contre l'arrêt cantonal du 1er novembre 2016, X._ et Y._ déposent un recours en matière pénale devant le Tribunal fédéral. Ils concluent, principalement, à l'annulation de l'arrêt attaqué et de l'ordonnance de classement ainsi qu'au renvoi de la procédure au Ministère public genevois pour mener tout acte d'instruction utile. A titre subsidiaire, ils demandent l'annulation de l'arrêt attaqué et le renvoi de la cause à l'autorité précédente pour nouvelle décision.