Lab 3: Recursion
Over the years, Tim has given many speeches. His talks cover a wide range of topics, some of which are particular fan-favorites and have been delivered multiple times. Much like how Tim’s most renowned talks might have been delivered hundreds of times in the same fashion, recursion has a similar repetitive nature. Using HTML trees, explore the idea of recursion, including when it is needed and when it isn’t.
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.
Just like Lists in Pyret, a HTML tree is 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
Create a new folder named recursionLab and open it in VSCode. Download or copy the lab03.py stencil file and the htmltree.py library file and save them in the newly-created folder. 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.