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