Chapter 7

# Recursion

## 7.1 Mathematical Functions

Consider the factorial function

$n!=n·\left(n-1\right)·\left(n-2\right)···2·1$

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:

$n!=\left\{\begin{array}{cc}1& \text{if}n=0\\ n·\left(n-1\right)& \text{if}n>0\end{array}$

If we use this definition to evaluate 3!, it unravels like this:

$\begin{array}{l}\begin{array}{ccc}\text{3}!& =& \text{3}·\text{2}!\hfill \\ =& \text{3}·\text{(2}·\text{1}!\text{)}\hfill \\ =& \text{3}·\text{(2}·\text{(1}·\text{0}!\text{))}\end{array}\\ \begin{array}{cc}=& 3\end{array}·\left(2·\left(1·1\right)\right)\begin{array}{cc}=& 6\end{array}\end{array}$

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 ...

Get A Concise Introduction to Data Structures using Java now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.