  This paper studies the expressive and computational power of discrete
Ordinary Differential Equations (ODEs), a.k.a. (Ordinary) Difference Equations.
It presents a new framework using these equations as a central tool for
computation and algorithm design. We present the general theory of discrete
ODEs for computation theory, we illustrate this with various examples of
algorithms, and we provide several implicit characterizations of complexity and
computability classes.
  The proposed framework presents an original point of view on complexity and
computation classes. It unifies several constructions that have been proposed
for characterizing these classes including classical approaches in implicit
complexity using restricted recursion schemes, as well as recent
characterizations of computability and complexity by classes of continuous
ordinary differential equations. It also helps understanding the relationships
between analog computations and classical discrete models of computation
theory.
  At a more technical point of view, this paper points out the fundamental role
of linear (discrete) ODEs and classical ODE tools such as changes of variables
to capture computability and complexity measures, or as a tool for programming
many algorithms.
