Your first question is:
How does fasting alone merit a recovery?
The Gemara in Berachos 17a writes:
when the Temple is standing, one sins and offers a sacrifice.
But, when the Temple is not standing, just like in our days, the Gemara explains the significance of fasting:
And now, I sat in observance of a fast and my fat and blood diminished.
May it be Your will that my fat and blood that diminished be considered as if I offered a sacrifice before You on the altar,
and may I find favor in Your eyes.
Similair, the Gemara in Zevachim explains that the Olah offering atones for the violation of positive commandments, and is a gift that a person offers to thank, after he is pardoned:
Rather, conclude from it that a burnt offering is a gift that one brings in order to appease God even after he is forgiven.
The Alter Rebbe (Igeret HaTeshuva, chapter 2) explains these two Gemara as:
Today, when we have no offerings to call forth G‑d’s pleasure, fasting replaces the offering. As the Talmud says, the prayer of one who is fasting is: “May my loss of fat and blood brought about through fasting be regarded as though I had offered it to You [as a sacrifice on the altar].
The purpose of fasting, then, is that one become acceptable to G‑d just as before the sin.
Furthermore, the Alter Rebbe explains:
On this basis, that fasting substitutes for an offering and as such has a place even when an individual does not need to undergo suffering in order to attain complete atonement,
The Alter Rebbe explains that fasting is wondrously effective for the revelation of the supreme will, and hereby quotes Vayikra 1:13:
of a sweet savour to the L-rd.
The "Lessons in Tanya" version adds a different light to these teachings:
Though fasting is not at all necessary for attaining atonement, it was explained above that nevertheless, it has a salutary effect as a substitute for the olah offering. In Temple times, this sacrifice was offered (even) for transgressing a positive command in order to make the former offender once again acceptable and beloved of G‑d. Accordingly, the Arizal derived from the Kabbalah the number of fasts to be undertaken for numerous transgressions, even those that are not subject to the punishment of excision or death by Divine decree.
A different approach on the result of fasting, can be found in chapter 1 of Likutei Amarim (Tanya) by the Alter Rebbe, namely that David HaMelech (King David) was devoid of an evil nature:
[...] having slain it through fasting.
In Sefer HaMiddot it explains that fasting is beneficial for all things:
הַתַּעֲנִית מוֹעִיל לְכָל דָּבָר
Fasting is beneficial for all things.
And that fasting is harder than the sword:
הַתַּעֲנִית קָשָׁה מֵחֶרֶב.
Fasting is harder [on the body] than the sword.
A deeper, more spiritual meaning of fasting, can be found in Likutei Halakhot
One merits this through fasting, etc. Because of the lusting (craving) for food and drink the kelipot are strengthened. They are the aspect of the 'ministers of Pharaoh' and they draw down speech beneath the aspect of the straightening of the throat, and one is not able to speak a word before Hashem Yisbarach, etc. The rectification for this is fasting, for through starving oneself, through drawing down the water of the Hasidim to moisten the throat, one fulfill (Isaiah 58:1) "Cry with full throat, without restraint", etc. Through this, faith is fully rectified, etc., as is brought there well, see there. Therefore it is forbidden to eat and drink before prayer, because one has to starve himself before prayer, which is the aspect of fasting hours every day; one starves oneself and investigates (oneself) before prayer.
The Shelah (Shenei Luchot HaBerit, Torah Shebikhtav, Ki Teitzei, Torah Ohr) adds that the gematria (numerical value) of the words voice, fasting and money, is 136- sharing a connection with prayer, acts of kindness (charity) and repentance
In Kav HaYashar it states that through fasting, one can protect himself against evil (sin):
However, this raises the concern that in consequence of the copious eating and drinking and rejoicing, Israel may come to sin. Therefore the Holy One Blessed is He preceded this day with a fast, because fasting has the power to protect a person from sin.
Concluding, fasting can be seen as a way of doing teshuva for the "materialistic sins", as the Orchos Tzadikim writes:
Repentance through the weighing of values — what is meant by that ? This means that he should suffer pain in proportion to the pleasure that he derived from the sin. He should afflict himself by fasting and by the lessening of food and drink, and in cohabitation and in all manner of pleasures, he should reduce the amount.
This too, can be found in what R' Nachman of Breslov writes:
Because of the lusting (craving) for food and drink the kelipot are strengthened.
Thus, fasting can weaken the kelipos that are strengthened by lusting and craving the materialistic, instead of the spiritual.