This article presents a direct adaptive control scheme for adaptive tracking of a class of discrete time nonlinear systems. We use structurally dynamic on-line function approximators and a gradient method with deadzone for adaptation. It is shown that all the signals in the system will be bounded and the tracking error will converge to a neighborhood of the origin whose size depends on the bounds on the disturbances in the system and the "ideal" approximation error. Moreover, it is shown that certain approximators that have a localization property are more suitable for the presented control scheme. Then we extend the algorithm such that the size of the deadzone is also adapted on-line while preserving the properties of the algorithm. The applicability of the theory is demonstrated with a simulation example.