I'm going to change the order a bit, if you don't mind.
What do you recomend?
Very plain, honest, polite... you are asking someone who's job or role it is to make recomendations to tell you what their answer is. This is short for "I know that you are the person responsible for this answer, or at least a person whose opinion I greatly value, so I would like to know your answer."
Very frequent, very, very polite... you are telling someone you value their judgement... you are almost telling them that you will accept their opinion over your own.
What will you recomend?
Very plain, honest, polite. You are asking about a recomendation that has been decided, but not given yet. "When you talk to your mother, what will you recomend?" Very frequent, very honest.
What would you recomend?
This is short for "What WOULD you recomend IF it was your job to recomend something, but don't forget that it is NOT your job, not YOUR decision."
I use this language when I ask a coworker for his opinion, BUT I don't want to lose control of the decision.. it is MY decision, I don't mind if he tells me what he thinks but I want to remind him that it is MY decision.
Or, this would be the language you would use if it is neither of your jobs to make the recomendation, but, again, you'd like to know his opinion anyway, even though it is not his job.
You watch a sporting event, you want to talk about what the player should do, you would ask, "What would you recomend?" Again, a way to get his opinion without saying that the decision is now his... it is the player's decision.
Very common, certainly polite, but can also have a sharp edge to it if you are trying to remind someone that you might NOT take their advice. I have an employee who almost insults me by asking me "what would you recomend, boss?" when he wants to let me know that he still might decide something different from me. If he was wanting to let me know that he knew I was the boss, he would change it to "what DO you recomend?" or "What IS your recomendation?"