Faits : A. X._, né en 1992 et domicilié en Valais, a été victime d'un accident de la route, le 3 août 2011, qui lui a causé une paraplégie complète. Le 7 novembre 2012, l'intéressé a adressé un certificat médical à l'Office cantonal des affaires militaires du canton du Valais (ci-après: l'Office cantonal). Le 17 décembre 2012, il a été déclaré inapte au service. B. La Section cantonale de la taxe d'exemption de l'obligation de servir du canton du Valais (ci-après: la Section cantonale) a taxé l'intéressé pour les années 2011 à 2014. Les décisions de taxation pour les années 2012 et 2013 ont été notifiées les 27 novembre 2013, respectivement 17 septembre 2014. X._ s'est acquitté de la totalité de la taxe d'exemption de l'obligation de servir de l'année 2012 et d'une partie de celle de l'année 2013. C. Le 15 décembre 2014, X._ a notamment demandé à la Section cantonale de reconsidérer les taxes d'exemption pour les années 2012 à 2014, de rectifier les taxations pour ces années et de rembourser les versements effectués à tort. Par deux décisions du 6 janvier 2015, la Section cantonale, après avoir considéré l'écriture de l'intéressé comme une réclamation, a déclaré irrecevables les réclamations pour les années 2012 et 2013. Dans une décision subséquente du 30 mars 2015 (art. 105 al. 2 LTF), elle a exonéré X._ de la taxe d'exemption de l'obligation de servir pour l'année 2014. L'intéressé a contesté les décisions sur réclamation relatives aux années 2012 et 2013 auprès de la Commission cantonale de recours en matière fiscale du canton du Valais (ci-après: la Commission de recours) le 19 janvier 2015. Par arrêt du 14 octobre 2015, la Commission de recours a admis le recours de X._. Elle a jugé en bref que l'Office cantonal n'avait pas transmis le certificat médical au Service cantonal, ce qui avait empêché ce dernier d'exonérer l'intéressé de la taxe d'exemption de l'obligation de servir. Les décisions de taxation ont ainsi été rendues sans qu'il ne soit tenu compte d'un fait important, établi par pièce. Reprocher à l'intéressé de ne pas avoir vérifié que les autorités aient correctement pris en compte les informations transmises aurait été contraire à la bonne foi et au principe de l'interdiction de formalisme excessif. D. Agissant par la voie du recours en matière de droit public, l'Administration fédérale des contributions demande au Tribunal fédéral, sous suite de frais, d'annuler la décision du 14 octobre 2015 de la Commission de recours, de confirmer les décisions de taxation des 27 novembre 2013 et 17 septembre 2014 et de confirmer les décisions sur réclamation du 6 janvier 2015. Elle se plaint de violation du droit fédéral. La Section cantonale conclut implicitement à l'admission du recours. La Commission de recours et X._ concluent tous deux au rejet du recours.