This work provides a framework for nominal and robust stability analysis for a class of discrete-time nonlinear recursive observers (DNRO). Given that the system has linear output mapping, local observability and Jacobian matrices satisfying certain conditions, the nominal and robust stability of the DNRO is defined by the property of estimation error dynamics and is analyzed using Lyapunov theory. Moreover, a simultaneous state and parameter estimation scheme is shown to be Input-to-State Stable (ISS), and adaptively reduce plant-model mismatch on-line. Three design strategies of the DNRO that satisfy the stability results are given as examples, including the widely used extended Kalman filter, extended Luenberger observer, and the fixed gain observer. (C) 2010 Elsevier Ltd. All rights reserved.