View presentation

Section 1: Background

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.

Section 2: Recursion Practice

Part 1: 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.

Part 2: Implementing Functions

Task 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.

Task 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.

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

Section 3: You’re All Set!

Success! Another lab complete! Please call over a TA to get checked off once you have completed all of your tasks.