# Trouble with Fractals

### Prerequisites

• The project requires you to be able to run Python on your computer, but does not require any programming skill.
• This project requires the following Python modules to be installed on your computer:
pygame

Need help with Python?

### Background

Recursion and runtime are two important concepts in computer science. Recursion is a strategy of solving a problem where doing a task involves doing a smaller version of that task, which involves doing an even smaller version of the task … until the task becomes so small that it can be done very easily.

For example, say Bob picked a number from 1 to 100 and Amy’s job is to guess it. Each time Amy guesses, Bob will tell Amy whether her guess is too high or too low. So, if Amy’s first guess is 50, Bob might say “too high.” Now, Amy’s problem is to pick a number from 1 to 49. This is just a smaller version of her first job! This means that Amy doesn’t have to come up with a new strategy for each guess; she can use the same logic for each smaller job, or “level of recursion.” Once Amy has guessed enough that her job is to pick a number from, say, 37 to 37, the job is so small that she doesn’t even need a strategy, and she is done. This is an example of a problem that can be solved using recursion.

Runtime is simply how long a program takes to run. Choosing a different strategy, or “algorithm,” can make a program run much faster or slower.

### Measuring Runtime Scaling

The King of Programmia wants to create a new national flag. He was recently introduced to the idea of fractals, so he got one of his advisors to write a program to draw a Sierpinski triangle. The program is recursive and lets the user decide how many levels they want to draw. Two levels looks like this:

while four levels look like this:

The King wanted the coolest-looking Sierpinski triangle possible, so he asked the program for 20 levels. After waiting for a full minute without the program finishing, he quit it and threatened to throw the writer in the dungeons for giving him a broken program. The writer of the program has asked you to go to the king for him and explain why the program can’t draw 20 levels in a reasonable amount of time, even though drawing 5 levels takes less than a tenth of a second.

You decide you need some data.