The evaluation of a syntax tree is performed as a depth-first
walk of the tree. Before evaluating a node, each of its arguments must
first be evaluated. Thus, one may
think of the syntax tree evaluation algorithm as a recursive call
on the root node of the tree, which in turn evaluates each of its
children, typically from left to right. Function and terminal nodes
return their values
up the tree to their parent, where terminals can only return their
value.
In the domain of mathematical functions, the expression
can be represented by an S-expression in prefix as:

which can then be represented as a syntax tree as:

The representation of candidate solutions in genetic programming is
not limited to
single syntax trees. Auxiliary data structures
such as memory arrays are also used [Spector and Luke, 1996], as are
data structures containing several syntax trees
to represent one solution [Luke, 1998]. The encapsulation of functions has been
accomplished with *automatically defined functions* [Koza, 1994] or
*automatically defined macros* [Spector, 1996].
More recent advances have seen
``architectural-altering'' operators, loops and recursion [Koza et al., 1999].
Additionally, when using functional languages such as ML in a genetic programming
framework, iteration and recursion can become more natural
[Olsson, 1995].