For machining of complex surface part with high accuracy and high quality, the numerical control (NC) interpolation algorithm of ultra-precision complex surface is very important. In the paper, a new method to model complex surface based on recursive subdivision theory is realized. This method can deal with complex surface with arbitrary topological structure which initial mesh controls, it has high calculation efficiency, modeling results are very ideal, and numerical control interpolation accuracy of the complex surface is very high and its error is controllable. During process of the NC code, the initial mesh model created by PRO/E or UG, through the date exchange and mesh model's recursive subdivision algorithm, until it reaches the ideal surface and ideal NC program code can be generated easily. Therefore the machining complex surface is smooth. Moreover, applicability of this algorithm is very extensive. Finally, experiments proved that high quality complex surface can be machined using this NC interpolation algorithm.