Abstract: The harmonic balance method is the most commonly used method for solving periodic solutions of nonlinear dynamic systems, but the high-order approximation of nonlinear terms requires sophisticated formula derivations, which limits its ultra-high accuracy computation. The authors' team proposed the reconstruction harmonic balance (RHB) method through the equivalent reconstruction of the frequency domain nonlinear quantity in the time domain, which successfully conquered the problem of ultra-high-order calculation of the classical harmonic balance method. However, both two methods require the dynamical system to be polynomial nonlinear, and cannot be directly used to solve the quasi-periodic solution of the nonlinear system. In view of the above problems, this paper proposes a novel method that combines the RHB method and the recast technique for complex nonlinear systems. First, the general nonlinear problem is non-destructively recast into a polynomial nonlinear system, and then the RHB method is used for high-precision solutions. Aiming at computing the quasi-periodic response, which is hard to obtain relatively accurate results by considering only one base frequency, the RHB method based on the idea of "supplemental frequency" is derived. By optimizing and selecting base frequencies, the fast and accurate capture of quasi-periodic response is achieved in this paper. The typical systems such as the nonlinear pendulum, and the nonlinear coupling asymmetric pendulum are selected for simulation and algorithm verification. Simulation results show that the accuracy of the proposed RHB-recast method achieves an accuracy up to 10⁻¹² when solving the non-polynomial type nonlinear systems, reaching the computer round-off-error accuracy, far exceeding the state-of-the-art methods. The supplemental frequency RHB method has been shown to produce efficient solutions for quasi-periodic problems, expanding the scope of the RHB-like methods for solving complex physical responses.