Programming and Problem Solving with Java

(^636) | Recursion

13.1 What Is Recursion?

You may have seen a set of gaily painted Russian dolls that fit inside one another. Inside the

first doll is a smaller doll, inside of which is an even smaller doll, inside of which is yet a

smaller doll, and so on. A recursive algorithm is like such a set of Russian dolls. It repro-

duces itself with smaller and smaller examples of itself until a solution is found—that is, un-

til no more dolls remain. The recursive algorithm is implemented by using a method that

makes recursive calls to itself.

Power Function Definition

Let’s examine a method that calculates the result of raising an integer to a positive power.

If xis an integer and nis a positive integer, then

xn=x*x*x*x*...*x

ntimes

We could also write this formula as

xn=x*(x*x*x*...*x)

n1 times

or even as

xn=x*x*(x*x*...*x)

n2 times

In fact, we can write the formula most concisely as

xn= x*xn^1

This definition of xnis a classic recursive definition—that is, a definition given

in terms of a smaller version of itself.

xnis defined in terms of multiplying xtimes xn^1. How is xn^1 defined? Why,

as x*xn^2 , of course! And xn^2 is x*xn^3 ; xn^3 is x*xn^4 ; and so on. In this exam-

ple, “in terms of smaller versions of itself” means that the exponent is decre-

mented each time.

When does the process stop? When we reach a case for which we know the

answer without resorting to a recursive definition. In this example, it is the case

Recursive definition A defini-

tion in which something is de-

fined in terms of smaller

versions of itself