This paper investigates the feasibility of using Genetic Programming in dynamically changing environments to evolve decision trees for classification problems and proposes an new version of Genetic Programming called Adaptive Genetic Programming. It does so by comparing the performance or classification error of Genetic Programming and Adaptive Genetic Programming to that of Gradient Descent in abruptly and progressively changing environments. To cope with dynamic environments, Adaptive Genetic Programming incorporates adaptive control parameters, variable elitism and culling. Results show that both Genetic Programming and Adaptive Genetic Programming are viable algorithms for dynamic environments yielding a performance gain over Gradient Descent for lower dimensional problems even with severe environment changes. In addition, Adaptive Genetic Programming performs slightly better than Genetic Programming, due to faster recovery from changes in the environment.