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 .