We introduce a constructive function approximation approach as a general tool, particularly useful in adaptive and data-driven methods for perception and control. The key idea is to estimate of a collection of simple local models as opposed to a single and complex regression model trained in the entire input space. We use principles from the Online Deterministic Annealing (ODA) optimization framework to construct an adaptive partition of the input space, which enables the introduction of local function approximation models within each subset of the partition. We show that both the partitioning and the local model training algorithms are stochastic approximation algorithms that operate online, and with the same observations, as part of a two-timescale stochastic approximation scheme. This process constitutes a heuristic method to gradually increase the complexity of the function approximation framework in a task-agnostic manner, giving emphasis to regions of the input space where the regression error is high. As a result this framework has inherent explainability properties, and is suitable for continuous learning applications where regression improvement without retraining from scratch is crucial. Simulation results illustrate the properties of the proposed approach.