Any progressive complete body overload by weight lifting program will tear up the muscles, requiring repair, and getting stronger, and building more.
It's that last part you require for recomp, which is burning a tad more fat to support the building of a tad more muscle.

Indeed eat at TDEE, or confirm weight stays in a 2-5 range, without waist increasing in size (if that is where you gain fat first).

As to what is best - it's totally up to your mental ability to handle it.

Bulk and cut is more efficient in terms of time.
As a woman you could add about 1 lb of muscle every 2-4 weeks depending on several factors, gotta get every workout in and make it count.
Of course you'll be adding lbs of fat at the same time, and size will go up because of that.
But you know you've lost before, and can do it easier in a cut with more muscle.
But, performance will suffer in a cut.
You may get used to eating level of surplus, and maintenance seems low, cut really seems bad.
But you can make the cut really minor so those negatives aren't that bad - but then it's not as efficient.

Recomp is much slower and may be hard to see results.
Could trade muscle weight for fat weight of rate of maybe 1 lb every 8-10 weeks, same factors as above.
But no weight or appreciable size gains, except in muscles being used.
May be hard to see progress, except on bar at first. After 6-9 months of lifting experience that will slow down anyway.
The 1 lb of fat lost could appear to be a lot though if in the right spot, so maybe not that bad.

Confirm you are at healthy goal weight though for either.

Because if basically starting lifting - you have unique position to actually keep losing fat and weight, while gaining some muscle.
That only happens at the start of lifting as newbie and having some fat to lose - it won't happen later.

Forget zig-zagging - you need consistent overage for bulking.

You can tweak recomp by eating more in the 24 hrs post lifting than the 24 hrs pre lifting - but still maintenance.

Carb cycling is usually part of that too, because contrary to popular opinion, it's not just about increased protein - but increased carbs too. Just when you bulk - those are automatically taken care of.

As to what is best - only you can answer that, with the points I shared above.

After trying to lose weight - can you mentally take purposely trying to gain weight and fat, and muscle?

The bulk does come first, because you gain fat, which must then be cut later.
Which also means can you take eating in comparison a whole lot less. Some get used to eating more and really enjoying it, and find it very hard to cut, past maintenance, and in to a deficit again.

And you don't want to bulk when carrying extra fat - the insulin insensitivity from having more fat means part of it's job of putting carbs and protein where they need to be isn't as good as when you have less fat.

That's why it's not good to bulk until down at bottom of healthy range of BF%.

Being that you are going back to the gym, depending on how long you've been away and your level before leaving, just about any overloading program will get you started. You will most likely see great "noob gains". Meaning at the beginning it doesn't take a ton of detail to start the process of building muscle, but as you progress is when you have to be more strategic. As @heybales has said when eating at TDEE should work. It may take longer, but it will work. I would suggest eating at TDEE and take full advantage of the "noob gains" by killing every workout and adding a bit more volume in the beginning. Look for a split that offers strength building days and hypertrophy days or weeks (low reps vs high reps). Good luck and keep us posted!