Lab 03

Lab 3: Recursion

As you’ve been touring the world, you haven’t been alone. You’ve been locked in a race against TheLegend27. You desperately want to be the first person to end TheLegend27’s Amazing Race gold medal streak, but that could be difficult because you somehow ended up on . . . Pluto? What?

Okay well to get back to your trip you’ll need to rebuild your spaceship so it can get you all the way back to Earth. You don’t have enough fuel to carry your entire ship back, so you will have to build a recursive spaceship. By building spaceships inside your spaceship, you can shed the outer layers of your spaceship and still fly safely in a smaller spaceship, using less fuel! “Alexa, play ‘What doesn’t kill you makes you Recursion’ please”

Recursive Data Structures

If you took CSCI 0111, you learned how to use recursion to iterate through a List in Pyret. That works because a non-empty List in Pyret consists of two components: the first element in the list, and the rest of the list. Lists are a recursive data structure because the rest of the list is itself a List.

Another recursive data structure is the HTML tree, which was introduced in lecture. The slides (link to slides) contain a recap of the HTML tree.

In this lab, you will use HTML trees in order to solve a few problems which require recursion (and a couple which don’t) to help you practice recursion, see when it is needed, and see when it isn’t.

Getting Started

Access the lab03.py stencil and the htmltree.py library from the following links: lab03.py and htmltree.py. Create a new project in PyCharm named recursionLab. Then, create two files named lab03.py and the htmltree.py and copy the stencil code into the files, respectively. Now you can start coding!

Testing

You can test your functions by using the parse function from the htmltree library. It takes in HTML as a string and returns an HTMLTree.

Problem 1

Complete the all_bold_text function, which returns all of the text (i.e., the text field on nodes with tag "text") inside <strong> tags (i.e., children of a <strong> tag, children of the children of a <strong> tag, etc.). Your function should call the all_text function (which we wrote in class, and is included in the stencil code) as a helper function.

Problem 2

Complete the get_longest_ul_length function, which should find the <ul> (unordered list) tag in the tree with the most children and return that number of children.

Problem 3

Complete the strong_to_emph function, which changes all the <strong> tags in a tree to <emph> tags.

Handing In

If you are working on labs asynchronously, head to TA hours to get checked off.