The kernel recursive least squares (KRLS) algorithm is used to improve the convergence rate and filtering accuracy of kernel adaptive filters (KAFs) in the Gaussian noise case. However, the linear growing network size in KRLS poses a huge amount of time and storage consumption. To address this issue, a novel Nystr ${\rm {{ \ddot{\bf{o}}}}}$ m kernel recursive least squares (NysKRLS) algorithm is proposed by approximating the Gaussian kernel with the Nystr ${\rm {{ \ddot{\bf{o}}}}}$ m method. In addition, the $k$ -means sampling is adopted in NysKRLS to develop another Nystr ${\rm {{ \ddot{\bf{o}}}}}$ m kernel recursive least squares with $k$ -means sampling (NysKRLS-KM) algorithm for further improving the approximation accuracy. NysKRLS-KM with a fixed dimensional network structure can achieve significantly better performance than the KAFs based on the stochastic gradient descent (SGD) method, and almost the same performance as KRLS efficiently. Monte Carlo simulations on nonlinear system identification and prediction of real-world data illustrate the superiorities of the proposed NysKRLS-KM algorithm from the aspects of computational and spatial complexity.