164
Recursion, Recurrence Relations, and Analysis of Algorithms
programming language ALGOL. In BNF notation, items that are defined in terms of
other items are enclosed in angle brackets, while specific items that are not further
broken down do not appear in brackets. The vertical line 0 denotes a choice, with the
same meaning as the English word or. The BNF definition of an identifier is
::5 0 0
::5 a 0 b 0 c 0 c 0 z
::5 1 0 2 0 c 0 9
Thus the identifier me2 is built from the definition by a sequence of choices such as
can be
which can be
2
which can be
2
which can be
e2
which can be
e2
which can be
me2
As a further connection between recursion and induction, there is a form of
induction called structural induction that can be applied to recursively defined
sets. Suppose we have a recursively defined set S and there is some property P(x)
that may or may not hold for x a member of S. If we can prove
1. Property P holds for all members of S described in the basis.
2. If property P holds for some members of S, then it holds for new members
of S constructed from these members using the recursive step.
then property P holds for all members of S.
example 8
A set S of strings is defined recursively by
1. λ belongs to S.
2. If x belongs to S, so do 1x0 and 0x1.
We can use structural induction to prove that every string in S consists of an
equal number of 0s and 1s. The basis, rule 1, identifies only a single string in S,
namely λ, which consists of an equal number of 0s and 1s (zero 0s and zero 1s).
Assume that string x consists of an equal number of 0s and 1s. Using rule 2, the two
new strings that can be constructed from x each add a single 1 and a single 0, so the
number of 0s and the number of 1s has each been increased by 1 and they are still
equal. By structural induction, every string in S has an equal number of 0s and 1s.
Notice that not all strings with an equal number of 0s and 1s belong to S. For
example there is no way to generate the string 1001 using the given rules.
Ordinary mathematical induction proves properties about integer values, and
the integers are ordered: 1, 2, … , k, k + 1, … . A set, however, isn’t necessarily
ordered. If we consider the set S defined in Example 8, it looks like
Recursion, Recurrence Relations, and Analysis of Algorithms
programming language ALGOL. In BNF notation, items that are defined in terms of
other items are enclosed in angle brackets, while specific items that are not further
broken down do not appear in brackets. The vertical line 0 denotes a choice, with the
same meaning as the English word or. The BNF definition of an identifier is
Thus the identifier me2 is built from the definition by a sequence of choices such as
can be
which can be
which can be
which can be
which can be
which can be
me2
As a further connection between recursion and induction, there is a form of
induction called structural induction that can be applied to recursively defined
sets. Suppose we have a recursively defined set S and there is some property P(x)
that may or may not hold for x a member of S. If we can prove
1. Property P holds for all members of S described in the basis.
2. If property P holds for some members of S, then it holds for new members
of S constructed from these members using the recursive step.
then property P holds for all members of S.
example 8
A set S of strings is defined recursively by
1. λ belongs to S.
2. If x belongs to S, so do 1x0 and 0x1.
We can use structural induction to prove that every string in S consists of an
equal number of 0s and 1s. The basis, rule 1, identifies only a single string in S,
namely λ, which consists of an equal number of 0s and 1s (zero 0s and zero 1s).
Assume that string x consists of an equal number of 0s and 1s. Using rule 2, the two
new strings that can be constructed from x each add a single 1 and a single 0, so the
number of 0s and the number of 1s has each been increased by 1 and they are still
equal. By structural induction, every string in S has an equal number of 0s and 1s.
Notice that not all strings with an equal number of 0s and 1s belong to S. For
example there is no way to generate the string 1001 using the given rules.
Ordinary mathematical induction proves properties about integer values, and
the integers are ordered: 1, 2, … , k, k + 1, … . A set, however, isn’t necessarily
ordered. If we consider the set S defined in Example 8, it looks like