A Concise Introduction to Data Structures using Java

Chapter 7

Recursion

7.1 Mathematical Functions

Consider the factorial function

$n!=n·(n-1)·(n-2)···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!=\{\begin{array}{cc}1& \text{if}n=0\\ n·(n-1)& \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}·(2·(1·1))\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 ...