Section 3.1 Recursive Definitions
179
if L[ i ] = x then
return 10
else
return g(L, i + 1, x)
end if
end if
end function g
79. Informally describe a recursive algorithm to reverse the entries in a list of items.
80. Informally describe a recursive algorithm to compute the sum of the digits of a positive integer.
81. Informally describe a recursive algorithm to compute the greatest common divisor of two positive integers
a and b where a > b. (Hint: The solution is based on the Euclidean algorithm, discussed in Section 2.3. In
particular, make use of expression (5) on page 134.)
82. The famous Towers of Hanoi puzzle involves 3 pegs with n disks of varying sizes stacked in order from
the largest (on the bottom) to the smallest (on the top) on 1 of the pegs. The puzzle requires that the disks
end up stacked the same way on a different peg; only one disk at a time can be moved to another peg, and
no disk can ever be stacked on top of a smaller disk. Informally describe a recursive algorithm to solve the
Towers of Hanoi puzzle.
83. Simulate the execution of algorithm SelectionSort on the following list L; write the list after every
exchange that changes the list.
4, 10, −6, 2, 5
84. Simulate the execution of algorithm SelectionSort on the following list L; write the list after every
exchange that changes the list.
9, 0, 2, 6, 4
85. The binary search algorithm is used with the following list; x has the value “Chicago.” Name the elements
against which x is compared.
Boston, Charlotte, Indianapolis, New Orleans, Philadelphia, San Antonio, Yakima
86. The binary search algorithm is used with the following list; x has the value “flour.” Name the elements
against which x is compared.
butter, chocolate, eggs, flour, shortening, sugar
87. Do a proof of correctness for the iterative function given in this section to compute S(n) of Example 1,
S(n) = 2
n
.
88. The Online Encyclopedia of Integer Sequences (OEIS) was originated and maintained for many years by
Neil Sloane, a mathematician at AT&T who has also written several books about sequences. The OEIS
Foundation now manages the database, which contains more than 200,000 sequences of integers that have
179
if L[ i ] = x then
return 10
else
return g(L, i + 1, x)
end if
end if
end function g
79. Informally describe a recursive algorithm to reverse the entries in a list of items.
80. Informally describe a recursive algorithm to compute the sum of the digits of a positive integer.
81. Informally describe a recursive algorithm to compute the greatest common divisor of two positive integers
a and b where a > b. (Hint: The solution is based on the Euclidean algorithm, discussed in Section 2.3. In
particular, make use of expression (5) on page 134.)
82. The famous Towers of Hanoi puzzle involves 3 pegs with n disks of varying sizes stacked in order from
the largest (on the bottom) to the smallest (on the top) on 1 of the pegs. The puzzle requires that the disks
end up stacked the same way on a different peg; only one disk at a time can be moved to another peg, and
no disk can ever be stacked on top of a smaller disk. Informally describe a recursive algorithm to solve the
Towers of Hanoi puzzle.
83. Simulate the execution of algorithm SelectionSort on the following list L; write the list after every
exchange that changes the list.
4, 10, −6, 2, 5
84. Simulate the execution of algorithm SelectionSort on the following list L; write the list after every
exchange that changes the list.
9, 0, 2, 6, 4
85. The binary search algorithm is used with the following list; x has the value “Chicago.” Name the elements
against which x is compared.
Boston, Charlotte, Indianapolis, New Orleans, Philadelphia, San Antonio, Yakima
86. The binary search algorithm is used with the following list; x has the value “flour.” Name the elements
against which x is compared.
butter, chocolate, eggs, flour, shortening, sugar
87. Do a proof of correctness for the iterative function given in this section to compute S(n) of Example 1,
S(n) = 2
n
.
88. The Online Encyclopedia of Integer Sequences (OEIS) was originated and maintained for many years by
Neil Sloane, a mathematician at AT&T who has also written several books about sequences. The OEIS
Foundation now manages the database, which contains more than 200,000 sequences of integers that have