How would you go about building a Music Recognition app

I am trying to build an app to recognize a song based on a user input. I would like to know how I should go about building this app. I have an idea that I must have the songs already in a source such as a database or cloud to compare them but what and how should I make the comparison isn't plain. I have seen apps for iPhones and other smart phones have this feature and even some websites but I am at a loss to how they actually manage to do this. Any help is appreciated.