6.5. Induction in Computer Science 193
Figure 6.2 Constructing the Koch Snowflake.Problem 6.8.
Fractals are an example of mathematical objects that can be defined recursively.
In this problem, we consider the Koch snowflake. Any Koch snowflake can be
constructed by the following recursive definition.
Base case: An equilateral triangle with a positive integer side length is a
Koch snowflake. Constructor case: LetKbe a Koch snowflake, and letlbe a line segment
on the snowflake. Remove the middle third ofl, and replace it with two line
segments of the same length as is done in Figure 6.2
The resulting figure is also a Koch snowflake.Prove by structural induction that the area inside any Koch snowflake is of the
formq
p
3 , whereqis a rational number.Problem 6.9.
LetLbe some convenient set whose elements will be calledlabels. The labeled
binary trees, LBT’s, are defined recursively as follows:
Definition. Base case: iflis a label, thenhl;leafiis an LBT, and
Constructor case: ifBandCare LBT’s, thenhl;B;Ciis an LBT.
Theleaf-labelsandinternal-labelsof an LBT are defined recursively in the ob-
vious way:
Definition. Base case: The set of leaf-labels of the LBThl;leafiisflg, and its
set of internal-labels is the empty set.
Constructor case: The set of leaf labels of the LBThl;B;Ciis the union of the
leaf-labels ofBand ofC; the set of internal-labels is the union offlgand the sets
of internal-labels ofBand ofC.
The set oflabelsof an LBT is the union of its leaf- and internal-labels.
The LBT’s withuniquelabels are also defined recursively: