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!={ 1ifn=0n·(n-1)ifn>0

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

3!=3·2!=3·(2·1!)=3·(2·(1·0!))=3·(2·(1·1))=6

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.