O'Reilly logo

A Concise Introduction to Data Structures using Java by Mark J. Johnson

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required