Chapter 7

# Recursion

## 7.1 Mathematical Functions

Consider the factorial function

$n!=n\xb7(n-1)\xb7(n-2)\xb7\xb7\xb72\xb71$

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\xb7(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}\xb7\text{2}!\hfill \\ =& \text{3}\xb7\text{(2}\xb7\text{1}!\text{)}\hfill \\ =& \text{3}\xb7\text{(2}\xb7\text{(1}\xb7\text{0}!\text{))}\end{array}\\ \begin{array}{cc}=& 3\end{array}\xb7(2\xb7(1\xb71))\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.