,
which produces
the reversal of x (i.e. x spelled backward).
Recursive Definition
Question:
Recursively define the function REV(x) on strings x over the alphabet ,
which produces
the reversal of x (i.e. x spelled backward).
Solution:
Basis Clause: 
.
Induction: For any string 
and any symbol 
REV(xa) = aREV(x).
Note that each step mirror the recursive definition of 
.