Recursive algorithms

A recursive algorithm solves a problem by reducing it to an instance of the same problem with a smaller input.

They are defined by:

1. a basis step
2. a recursive step

For example, \(n!\) maybe defined by a basis of \(0! = 1\) and the recursive expression that \(n! = n \cdot (n - 1)!\). Similarly, Euclid’s algorithm provides an efficient, recursive approach to finding greatest common divisors.