There are recognized countries that are members of UN.
There are recognized countries that are not members of UN.
There are legal countries that are not widely recognized.
So, what is the relation between "recognition" and "legality" of a country"?
One of the definitions of "legality" basically means if a country declared its independence legally - maybe through a peace treaty, a referendum, etc.
It isn't that important in the foreign affairs aspect since diplomatic ties are based on "recognition". Ultimately, a country needs to be recognised to be able to gain membership in inter-governmental organisations or to travel freely to other nations.
"[Diplomatic] Recognition" as defined in Wikipedia:
Diplomatic recognition in international law is a unilateral political act with domestic and international legal consequences, whereby a state acknowledges an act or status of another state or government in control of a state (may be also a recognized state).
The UN also describes this on their website:
How does a new State or Government obtain recognition by the United Nations?
The recognition of a new State or Government is an act that only other States and Governments may grant or withhold. It generally implies readiness to assume diplomatic relations. The United Nations is neither a State nor a Government, and therefore does not possess any authority to recognize either a State or a Government. As an organization of independent States, it may admit a new State to its membership or accept the credentials of the representatives of a new Government.
This is more important in the diplomatic aspect as countries need to be recognised by a number of other countries in order to be a member of the United Nations.
An example would be Kosovo, which is recognised by 57% of UN member states but is still not a member of the UN.
In conclusion, "legality" basically means the legality of the existent of a state, but it doesn't really hold much meaning or value on the international stage while recognition means whether other countries accept you as a sovereign nation/ state or do they count you as territory of another country.
Your question includes three different concepts: UN membership, recognition, and legality. I will explain each one in turn as well as drawing distinctions or relationships between each thing.
The rules for joining the United Nations can be found here. The most relevant aspects are:
Although there are no formal rules for when a state should be admitted or not, the Charter does say this:
Membership in the United Nations is open to all other peace-loving states which accept the obligations contained in the present Charter and, in the judgment of the Organization, are able and willing to carry out these obligations. Source: Chapter II Art.4
United Nations membership just means that a state has been approved to be a member of the United Nations. They have agreed to adhere to the UN charter and have the approval of the Security Council and General Assembly. There is no notion of "legality" or "recognition", just the idea of being a state.
The generally-cited legal description of a state comes from the Montevideo Convention.
Article I defines a state:
The state as a person of international law should possess the following qualifications:
a ) a permanent population;
b ) a defined territory;
c ) government; and
d) capacity to enter into relations with the other states.
This is the closest you will come to a concept of "legality". The Convention expressly says that a state may be legal and not be recognized:
The political existence of the state is independent of recognition by the other states (Source: Article 3)
No single entity decides when a state is a state, and no single entity decides when a state is recognized. Rather, each state decides when to recognize a state. There is a distinct one-to-one relationship here: if something is a state, than every other state is required to recognize it (so there are no unrecognized states except in the short-term), and everything recognized as a state is a state (so there are no incorrectly recognized states) (See this analysis from the Yale Law Review).
Effectively, this means that any legal state must be recognized by other nations, and also that all members of the United Nations are recognized states.
The wikipedia article nicely sums up diplomatic recognition, which is mostly a matter of custom rather than formal law. Recognition is unilateral (Country A chooses to recognize Country B, this does not mean that Country B recognize or does not recognize Country A).
De facto recognition occurs from extra-legal acts. For example, if the President of the United States visits with heads of a country in an official sense, that is effective recognition of that state. Recognition can also occur through legal channels. For example, when a United Nations member votes in favor of admitting a state to the United Nations, they are offering a legal admittance that the state is (in fact) a state.
UN membership is only open to states. UN membership requires a vote from the General Assembly, and voting to admit a state is legal recognition of that state. So all members of the United Nations are both legal and recognized (by the majority of UN member nations) states.
Legal states may theoretically be unrecognized, although every state has an obligation to recognize a legal state. In practice, the evidence that a state is a legal state is recognition, so (in practice) there are no unrecognized legal states.
Recognized states are always legal states. However, not all recognized states may be members of the United Nations. It's possible that a recognized state can choose not to accept the United Nations charter or seek membership, or that it will fail to be admitted.
LEGALITY AND RECOGNITION ARE TWO COMPLETELY DIFFERENT THINGS
(Neither of them is a "necessary" or a "sufficient" condition for the other one)
Recognition is completely a political notion/act (as stated by International Court of Justice, Kosovo 2010 decision) and has nothing to do with legality.
So, even if no country recognizes a country, this has nothing to do with the legality of that country.
Then-President of the International Court of Justice (ICJ) Hisashi OWADA (2010): "International law contains no "prohibition on declarations of independence."
The International Court of Justice (ICJ) (2010): "while the declaration may not have been illegal, the issue of RECOGNITION was a POLITICAL one".
(in OSHISANYA 2016, An Almanac of Contemporary and Comperative Judicial Restatement, p.64)
Hence, "recognition is a political action/matter, not a legal matter".
That is to say, “being recognized/not recognized does not affect legality/illegality of a country”.
That said, as far as "legality" and "recognition" are considered, the existence of either of them helps the existence of the other.
