To guarantee the safety of flight operations, decision-support systems for air traffic control must be able to improve the usage of airspace capacity and handle increasing demand. In this study, we address the aircraft conflict avoidance and trajectory recovery problem. The problem of finding least deviation conflict-free aircraft trajectories that guarantee the return to a target waypoint is highly complex due to the nature of the nonlinear trajectories that are sought. We present a two-stage iterative algorithm that first solves initial conflict by manipulating their speed and heading control and then identifying each aircraft's optimal time to recover its trajectory towards their nominal. The avoidance stage extends existing mixed-integer programming formulations, and for the recovery stage, we propose a novel mixed-integer formulation. We assume that speed and heading control are continuous variables for this approach while the recovery time is treated as a discrete variable. In this approach, it is shown that the trajectory recovery costs can be anticipated by inducing avoidance trajectories with higher deviation, therefore obtaining earlier recovery time within few iterations. Numerical results on benchmark conflict resolution problems show that this approach can solve instances with up to 30 aircraft within 10 minutes.