A. Programming Concepts and Skills · Algorithm Design and Analysis

Recursive Algorithms: Numbers to Words, Fractals and XML

A3.6 C2.1About 75 minutes

Learning goals

I can write a recursive algorithm that translates numbers into words.
I can generate a fractal pattern with recursion and predict how its size grows.
I can process nested data such as an XML document with a recursive function.
I can explain why problems with a self-similar structure suit recursion.

Words to know

self-similar
Made of smaller copies of itself, like a fractal, a folder of folders, or a number made of groups of digits.

fractal
A shape in which each part is a smaller copy of the whole, generated by repeating a rule at smaller and smaller scales.

tree (data)
Nested data with one root; each element can contain child elements, which can contain their own children.

XML
Extensible Markup Language: a text format for nested data using tags such as <course> … </course>.

element / attribute
In XML, an element is a tag and everything inside it; an attribute is a name="value" pair inside the opening tag.

parse
To read text (such as an XML file) and build a data structure that represents its meaning.

Patterns inside patterns

Look closely at a fern frond: each small leaf looks like a tiny copy of the whole frond. A file folder can hold folders, which hold more folders. The number 2 026 026 is "two million, twenty-six thousand, twenty-six", and each part is a smaller number said the same way.

Problems with this self-similar structure are where recursion really shines. Expectation A3.6 names several: calculating a factorial (last lesson), translating numbers into words, performing a merge sort (next-but-one lesson), generating fractals and performing XML parsing. This lesson does three of them.

1. Translating numbers into words

To say a number such as 31 416, you split it into groups: "thirty-one thousand, four hundred sixteen". The part before "thousand" (31) and the part after it (416) are each smaller numbers, said by the same rules. That is a recursive algorithm:

Base cases: 0 to 19 are single words; 20 to 99 are a tens word plus maybe a ones word.
Recursive case: for the biggest unit (million, thousand or hundred) that fits, say words(n // unit), the unit's name, then words(n % unit) if it is not zero.

ONES = ["zero", "one", "two", "three", "four", "five", "six", "seven", "eight",

"nine", "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen",

"sixteen", "seventeen", "eighteen", "nineteen"]

TENS = ["", "", "twenty", "thirty", "forty", "fifty", "sixty", "seventy",

"eighty", "ninety"]

def words(n):

"""Return n (0 <= n < 1 000 000 000) in English words."""

if n < 20: # base case: a single word

return ONES[n]

if n < 100:

rest = "" if n % 10 == 0 else "-" + ONES[n % 10]

return TENS[n // 10] + rest

for size, name in [(1_000_000, "million"), (1000, "thousand"), (100, "hundred")]:

if n >= size:

rest = "" if n % size == 0 else " " + words(n % size)

return words(n // size) + " " + name + rest

for n in [7, 42, 905, 2026, 31_416, 1_000_001, 999_999_999]:

print(n, "->", words(n))

Its checked output is shown in the next box. n // size is the part before the unit word and n % size the part after. Both are smaller than n, so the recursion always reaches a base case. (Cheques in Canada are often written with "and" or with dollars and cents; changing the format only changes the base cases and joining words.)

7 -> seven

42 -> forty-two

905 -> nine hundred five

2026 -> two thousand twenty-six

31416 -> thirty-one thousand four hundred sixteen

1000001 -> one million one

999999999 -> nine hundred ninety-nine million nine hundred ninety-nine thousand nine hundred ninety-nine

Output of the program above (checked by running it).

Worked example

Tracing words(31416)

Show the recursive calls made by words(31416) and how the answer is assembled.

31416 ≥ 1000 (but < 1 000 000), so the unit is thousand: words(31416 // 1000) + " thousand " + words(31416 % 1000) = words(31) + " thousand " + words(416).
words(31): 20 ≤ 31 < 100, so TENS[3] + "-" + ONES[1] = "thirty-one". (Base case: no further recursion.)
words(416): ≥ 100, so the unit is hundred: words(4) + " hundred " + words(16) = "four" + " hundred " + "sixteen".
Assemble: "thirty-one" + " thousand " + "four hundred sixteen" = "thirty-one thousand four hundred sixteen".
Calls made: words(31416), words(31), words(416), words(4), words(16): 5 calls. The number of calls grows with the number of digit groups, about O(log n).

"thirty-one thousand four hundred sixteen", from 5 calls.

2. Generating fractals

A fractal is drawn by a rule that says "draw a smaller copy of me here, and here, and here". The recursion stops at a base case, usually when the shapes are small enough (or a level counter reaches 0).

Two text fractals you can run anywhere:

Ruler: a ruler of level n is a ruler of level n − 1, a long tick of length n, and another ruler of level n − 1. (Look at the markings between the inch marks on an imperial ruler: the half-inch tick is longest, then the quarters, then the eighths, and so on.)
Sierpinski triangle: order n is three copies of order n − 1: one on top, two side by side underneath.

def ruler(n):

"""Print the tick marks of a ruler with n levels."""

if n == 0: # base case: nothing to draw

return

ruler(n - 1) # left half: a smaller ruler

print("-" * n) # the big middle tick

ruler(n - 1) # right half: another smaller ruler

def sierpinski(n):

"""Return the lines of a Sierpinski triangle of order n."""

if n == 0:

return ["*"]

small = sierpinski(n - 1)

pad = " " * 2 ** (n - 1)

top = [pad + line + pad for line in small]

bottom = [line + " " + line for line in small]

return top + bottom

ruler(3)

for line in sierpinski(3):

print(line.rstrip())

Its checked output is shown in the next box. Each function calls itself on level n − 1. sierpinski builds a list of text lines: the top copy is padded with spaces to centre it over the two bottom copies.

---

* *

* * * *

* *

* * * *

* * * * * * * *

Output of the program above (checked by running it).

Sierpinski triangles of orders 0 to 3, drawn by the same rule as the text version: three half-size copies, arranged in a triangle.

How much work? ruler(n) calls itself twice on n − 1, so the number of ticks doubles with each level: 2ⁿ − 1 ticks (7 for n = 3, 1023 for n = 10). sierpinski(n) contains 3ⁿ stars. Fractal recursion is often exponential in the level, which is fine because the levels are small (each level halves the size, and you cannot see shapes smaller than a pixel). It would be a disaster for a problem where n is large; see Recursion Pitfalls: Infinite Recursion and Exponential Growth.

With Python's built-in turtle module (it opens a drawing window in IDLE or Thonny) the same pattern draws real fractals: to draw a Koch curve of a given length and level, draw four Koch curves of one third the length at level − 1, turning 60° left, 120° right and 60° left between them; at level 0 just move forward. The activity below lets you try it.

3. Parsing XML: recursion on nested data

XML stores nested data as text. Every element has a tag, may have attributes and text, and may contain child elements. Python's standard module xml.etree.ElementTree, which you used to read XML files in XML Files and Databases, parses the text into a tree of element objects: you can loop over an element's children with for child in element, read element.tag, element.attrib (a dictionary) and element.text.

Because each child is itself the root of a smaller tree, a function that processes "this element, then each child the same way" handles any depth of nesting, without knowing the depth in advance.

The XML document below as a tree. The root is school; each department is the root of its own smaller tree, and so is each course.

import xml.etree.ElementTree as ET

doc = """<school>

<unit>Algorithm Design and Analysis</unit>

<unit>Modular and Object-Oriented Design</unit>

</course>

</department>

</department>

</school>"""

def show(element, depth=0):

"""Print element and everything inside it, indented by depth."""

label = element.tag

for key, value in element.attrib.items():

label += " " + key + "=" + value

if element.text and element.text.strip():

label += ": " + element.text.strip()

print(" " * depth + label)

for child in element: # recursive case: each child is a smaller tree

show(child, depth + 1)

def count(element):

"""Return the number of elements in this tree (including this one)."""

return 1 + sum(count(child) for child in element)

root = ET.fromstring(doc)

show(root)

print("elements:", count(root))

Its checked output is shown in the next box. show prints each element indented by its depth, then calls itself on each child. count has no explicit base case: an element with no children (a leaf) has an empty for loop, so sum of nothing is 0 and it returns 1.

school

department name=Computer Studies

course code=ICS3U

course code=ICS4U

unit: Algorithm Design and Analysis

unit: Modular and Object-Oriented Design

department name=Mathematics

course code=MHF4U

course code=MCV4U

elements: 9

Output of the program above (checked by running it).

Why recursion for trees?

A loop works well when you know how many levels there are. A school document might have 3 levels today and 5 next year (if someone adds lessons inside units). The recursive show and count work for any depth, because they only ever deal with "this element and its children". The same pattern lists every file in a folder and all its subfolders, totals the sizes of nested folders, and evaluates nested math expressions.

Precondition and postcondition for count: precondition: element is an ElementTree element (well-formed XML was parsed). Postcondition: returns the number of elements in the subtree rooted at element, including itself; the tree is unchanged. Every element is visited exactly once: O(number of elements).

Just for fun

How do you make a Sierpinski triangle sandwich?

Cut the sandwich into four triangles and eat the middle one. Then do the same to each of the three that are left. Repeat until lunch is over. (Mathematically, you would end up eating the whole sandwich: the remaining area shrinks by a quarter at every step.)

Hands-on activity

Fractals on paper and on screen

You need: a sheet of paper, a ruler, a pencil, and a computer with Python (IDLE or Thonny for the turtle part).

Paper Sierpinski: draw a large equilateral triangle (sides about 16 cm). Join the midpoints of its sides and shade the middle triangle. Repeat on each of the three unshaded triangles, then on the nine smaller ones. How many unshaded triangles are there after 3 levels? (27.)
Numbers to words: extend words to handle negative numbers ("minus …") and numbers up to 999 billion. Test it on today's date as a number (e.g. 20261017) and on your birth year.
Turtle Koch curve (optional, needs a window): write koch(t, length, level): if level is 0, t.forward(length); otherwise call koch four times with length / 3 and level - 1, with t.left(60), t.right(120), t.left(60) between the calls. Start with import turtle, t = turtle.Turtle(), t.speed(0) and draw levels 0 to 4.
XML: write your own XML for a family recipe book (<recipes>, <recipe name=...>, <ingredient>), parse it with ET.fromstring, and write recursive functions that print it and count the ingredients.

What to look for: the Koch curve at level n is made of 4ⁿ straight segments; your XML functions work unchanged if you add a new nesting level (for example <section> around recipes).

Your turn

What does words(70) return? words(118)?

List the recursive calls made by words(5_000_000).

How many lines does ruler(4) print? How many dashes are on the longest line?

How many stars are in sierpinski(4)?

In the XML example, what is element.attrib for the ICS4U course element?

Why does count not need an if for its base case?

More practice: warm-up

What is a fractal?

Name three examples of self-similar data or shapes.

What does words(13) return?

Which Python module parses XML in the standard library?

What does ruler(1) print?

More practice: on your own

Trace words(2026): list each call and its return value.

Write a recursive depth(element) that returns how many levels deep an XML tree is (a leaf has depth 1). What is the depth of the school document?

Write find_all(element, tag) that returns a list of every element with the given tag anywhere in the tree.

How many straight segments make up a Koch curve of level 5? How many recursive calls (including the first) are made to draw it?

Predict the output:

def pattern(n):

if n == 0:

return "x"

return "(" + pattern(n - 1) + pattern(n - 1) + ")"

print(pattern(2))

Challenge

Write flatten(items) that turns any nested list into a flat list: flatten([1, [2, [3, 4]], 5]) = [1, 2, 3, 4, 5]. (Use isinstance(x, list).)

Explain why ruler(n) makes 2ⁿ⁺¹ − 1 calls in total (including calls with n = 0). Verify for n = 2.

Design a recursive function words_fr(n) for French numbers from 0 to 99. Which parts are base cases, and what is irregular?

Check your understanding

Quiz

Which list includes only examples that A3.6 names for recursive algorithms?

What does words(40_015) return?

How many ticks (lines) does ruler(5) print?

Why is recursion a natural fit for processing XML?

In a Sierpinski triangle of order n, how many smallest triangles are there?

What is the Big-O of the recursive count on an XML tree with N elements?

For parents and teachers

Big idea: A3.6 lists the algorithms students should be able to design recursively: factorial, translating numbers into words, merge sort, fractals and XML parsing. This lesson covers numbers into words, fractals and XML parsing (factorial was in Thinking Recursively and merge sort follows in Merge Sort: Divide and Conquer), with contracts for the tree functions (C2.1).

How to help: Do the paper Sierpinski triangle together and count the triangles at each level (1, 3, 9, 27). Ask your teen to say a big number in words and explain how they split it into groups; that is exactly the algorithm.

Common difficulties:

In numbers to words: adding an extra space or "zero" when the remainder is 0 ("two thousand zero").
Forgetting that each fractal level multiplies the work (2ⁿ or 3ⁿ calls).
In XML, confusing an element's text with its children, or forgetting to recurse into children.
Mixing up element.attrib (a dictionary) and element.text (a string or None).