Lab 3: Recursion

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.

An HTML tree is also a recursive data structure, because the children of the current 'node' of the HTML tree are also HTML trees.

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 Directory called lab03. 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 the text of all <text> tags that are descendants of <strong> tags (i.e. children, children of children 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.