Consider the factorial function
The “. . . ” in this expression is a bit informal, even though we intuitively know what it means. One way to precisely define factorial looks like this:
If we use this definition to evaluate 3!, it unravels like this:
Notice that the first part of the definition causes the unraveling to stop.
This definition is recursive because it defines factorial in terms of another factorial; in this case, n! is defined in terms of (n − 1)!. Recursive definitions have two key features:
Recursive steps use smaller arguments. In this example, the factorial of n is computed using ...