Simple Recursive Functions (e.g. Factorial, GCD, Binary Search, Conversion of Representations of Numbers Between Different Bases)

Many problems can be solved very elegantly by observing that the solution can be composed of solutions to ‘smaller’ versions of the same problem with the base version having a known simple solution. Recursion can be initially motivated by using recursive equations to define certain methods. These definitions are fairly obvious and are easy to understand. The definitions can be directly converted to a program. Emphasize that any recursion must have a base case. Otherwise, the computation can go into an infinite loop. The tower of Hanoi is a very good example of how recursion gives a very simple and elegant solution where as non-recursive solutions are quite complex.