Ch.5 Flashcards
We illustrate the execution of a recursive method using a [re…n t..e]. Each
entry of the trace corresponds to a recursive call. Each new recursive method call
is indicated by a downward arrow to a new invocation.
recursion trace 192
To demonstrate the mechanics of recursion, we
begin with a simple mathematical
example of computing the value of the [f…al f…on]. The factorial of a positive
integer n, denoted n!, is defined as the product of the
of the integers from 1 to n. If
n = 0, then n! is defined as 1 by convention.
factorial function 191
For example, 5! = 5 ·4 ·3 ·2 ·1 = 120. The factorial function is important because
it is known to equal the number of ways in which n distinct items can be arranged
into a sequence, that is, the number of [pe..s] of n items. For example, the
three characters a, b, and c can be arranged in 3! = 3 · 2 · 1 = 6 ways: abc, acb,
bac, bca, cab, and cba.
permutations 191
More generally, for a positive integer n,
we can define n! to be n ·(n−1)!. This [re..e d..n] can be formalized as
n! =
#
1 if n = 0
n ·(n−1)! if n ≥ 1.
recursive definition 191
This definition is typical of many recursive definitions of functions. First, we
have one or more b…se c..es, which refer to fixed values of the function. The above
definition has one base case stating that n! = 1 for n = 0. Second, we have one
or more [r..ve c..es], which define the function in terms of itself. In the above
definition, there is one recursive case, which indicates that n!=n(1)! for n≥1.
base cases, recursive cases 191
For each inch, we place a tick with a numeric label. We denote the length of the tick designating a whole inch as the [m..r t..k l..h]. Between the marks for whole inches, the ruler contains a series of [m..r t..s], placed at intervals of
1/2 inch, 1/4 inch, and so on ….
major tick length, minor ticks 193
The English ruler pattern is a simple example of a [f…l], that is, a shape that has a self-recursive structure at various levels of magnification.
fractal 193
For illustration, Figure 5.7 portrays the disk space being used by all entries in our sample file system. We differentiate between the [i…e] disk space used by
each entry and the [cu…e] disk space used by that entry and all nested features. For example, the cs016 directory uses only 2K of immediate space, but a total of
249K of cumulative space.
immediate, cumulative 198
In this section, we describe a classic recursive algorithm, [b…y s…h], used to efficiently locate a target value within a sorted sequence of [n e…s] stored in
an array.
binary search, n elements 196
When the sequence is [u..d], the standard approach to search for a target value is to use a loop to examine every element, until either finding the target or
exhausting the data set. This algorithm is known as [l..r s..h], or [s..l s..h], and it runs in O(n) time (i.e., linear time) since every element is inspected
in the worst case.
When the sequence is [s..d] and [i..e], there is a more efficient algorithm. (For intuition, think about how you would accomplish this task by hand!) If we
consider an arbitrary element of the sequence with value v, we can be sure that all
elements prior to that in the sequence have values less than or equal to v, and that all
elements after that element in the sequence have values greater than or equal to v.
unsorted, linear search, sequential search, sorted, indexable 196
We call an element of the sequence a [c..e]
if, at the current stage of the search, we cannot rule out that this item matches the target. The algorithm maintains two parameters, low and high, such that all the
candidate elements have index at least low and at most high. Initially, low = 0 and high = n−1. We then compare the target value to the [m..n c..e], that is,
the element with index
mid = ⌊(low+high)/2⌋
candidate, median candidate 196
