Pulling the power out will further destabilize the airplane, as you'll lose the nose-down force of the propwash going over the rear horizontal stabilizers, making it even more difficult to recover from the stall.
The first and foremost thing to do is relieve the angle of attack, and simultaneously apply maximum power if not already applied.