Would a letter of recommendation from my former Commanding Officer (who separated me) help me to reenlist with an RE-4?

According to the Navy, no go if you want to rejoin the active component.

An RE-4 means you are "Normally not eligible to reenlist, nor join another service" and will require a waiver to reenlist.

Specific to the Navy (active component), they consider RE-2, RE-3A, RE-3C, and RE-4* as "Ineligible to reenlist - waivers not authorized and will not be considered"*. However, the Navy does say that they will consider a waiver for RE-4 codes on a case by case basis to join the Navy Reserves.
---------------------------------
* Prior service applicants issued a Reenlistment code of RE-4 (or equivalent) upon separation, solely for homosexual conduct may be eligible for re-enlistment/enlistment.
* https://www.navycs.com/military-re-codes.html
* https://www.mynavyhr.navy.mil/Career-Management/Reserve-Personnel-Mgmt/Enlisted/Waivers/

Your commanding officer is the one that gave you that RE-4 code to begin with, so I doubt they'd give you the recommendation to re-up after they looked over your record. My CO gave me an RE4 bc I went over his head to get out of the service. He was going to extend my PRD out to my EAOS and send me overseas with the squadron for 6 months after I'd just had a baby. I would have been willing to go IF my husband at the time had not been a drunkard and unable to care for my 3 children properly. However, the CO was having none of that and did it anyway. I had to write a letter to the Chief of Naval Personnel to request an early out, which was approved. Needless to say, the CO wasn't happy and gave me the RE4 even though I was physically and mentally capable of reenlistment. That bastard ruined my chances of getting my 20 (I had 13). Still, I'd do it all over again if I had to. My kids came first.

The Army will sometimes waiver an RE-4 code, depending on how hard up they are for bodies and the reason code for the RE-4. It would probably be to your best interest to get that RE code changed if you are trying to get back in the Navy, they say they won't waivers for RE4.