178
Recursion, Recurrence Relations, and Analysis of Algorithms
66. Give a recursive definition for the addition of two nonnegative integers m and n.
67. a. Write a recursive definition for the operation of taking the maximum of n integers a 1 , … , a n , n ≥ 2.
b. Write a recursive definition for the operation of taking the minimum of n integers a 1 , … , a n , n ≥ 2.
68. a. Give a recursive definition for the conjunction of n statement letters in propositional logic, n ≥ 2.
b. Write a generalization of the associative property of conjunction (tautological equivalence 2b of
Section 1.1) and use induction to prove it.
69. Let A and B 1 , B 2 , … , B n be statement letters. Prove the finite extension of the distributive equivalences of
propositional logic:
A ~ (B 1 ` B 2 ` c ` B n ) 3 (A ~ B 1 ) ` (A ~ B 2 ) ` c ` (A ~ B n )
and
A ` (B 1 ~ B 2 ~ c~ B n ) 3 (A ` B 1 ) ~ (A ` B 2 ) ~ c~ (A ` B n )
for n ≥ 2.
70. Let B 1 , B 2 , … , B n be statement letters. Prove the finite extension of De Morgan’s laws:
(B 1 ~ B 2 ~ c~ B n )′ 3 B′ 1 ` B′ 2 ` c ` B′ n
and
(B 1 ` B 2 ` c ` B n )′ 3 B′ 1 ~ B′ 2 ~ c~ B′ n
for n ≥ 2.
In Exercises 71–76, write the body of a recursive function to compute S(n) for the given sequence S.
71. 1, 3, 9, 27, 81, …
72. 2, 1, 1/2, 1/4, 1/8, …
73. 1, 2, 4, 7, 11, 16, 22, …
74. 2, 4, 16, 256, …
75. a, b, a + b, a + 2b, 2a + 3b, 3a + 5b, …
76. p, p − q, p + q, p − 2q, p + 2q, p − 3q, …
77. What value is returned by the following recursive function Mystery for an input value of n?
Mystery (positive integer n)
if n = 1 then
return 1
else
return Mystery(n − 1) + 1
end if
end function Mystery
78. The following recursive function is initially invoked with an i value of 1. L is a list (array) of 10 integers.
What does the function do?
g(list L; positive integer i; integer x)
if i > 10 then
return 0
else