\n",
"\n",
""
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "8119ba50",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"from os.path import basename, exists\n",
"\n",
"def download(url):\n",
" \"\"\"Download a file if it isn't already here, and return its filename.\"\"\"\n",
" filename = basename(url)\n",
" if not exists(filename):\n",
" from urllib.request import urlretrieve\n",
"\n",
" local, _ = urlretrieve(url, filename)\n",
" print(\"Downloaded \" + str(local))\n",
" return filename\n",
"\n",
"download('https://github.com/porttack/working-in-python/raw/v3/working_in_python.py');\n",
"download('https://github.com/AllenDowney/ThinkPython/raw/v3/diagram.py');\n",
"download('https://github.com/ramalho/jupyturtle/releases/download/2024-03/jupyturtle.py');\n",
"\n",
"import working_in_python\n",
"# apcsp:begin type=\"note\" chapter=\"05\"\n",
"working_in_python.enable_docstring_reminders()\n",
"# apcsp:end"
]
},
{
"cell_type": "markdown",
"id": "75b60d6c",
"metadata": {},
"source": [
"# Conditionals and Recursion\n",
"\n",
"The main topic of this chapter is the `if` statement, which executes different code depending on the state of the program.\n",
"And with the `if` statement we'll be able to explore one of the most powerful ideas in computing, **recursion**.\n",
"\n",
"But we'll start with three new features: the modulus operator, boolean expressions, and logical operators."
]
},
{
"cell_type": "markdown",
"id": "4ab7caf4",
"metadata": {},
"source": [
"## Integer division and modulus\n",
"\n",
"Recall that the integer division operator, `//`, divides two numbers and rounds\n",
"down to an integer.\n",
"For example, suppose the run time of a movie is 105 minutes. \n",
"You might want to know how long that is in hours.\n",
"Conventional division returns a floating-point number:"
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "30bd0ba7",
"metadata": {},
"outputs": [],
"source": [
"minutes = 105\n",
"minutes / 60"
]
},
{
"cell_type": "markdown",
"id": "3f224403",
"metadata": {},
"source": [
"But we don't normally write hours with decimal points.\n",
"Integer division returns the integer number of hours, rounding down:"
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "451e3198",
"metadata": {},
"outputs": [],
"source": [
"minutes = 105\n",
"hours = minutes // 60\n",
"hours"
]
},
{
"cell_type": "markdown",
"id": "bfa9b0cf",
"metadata": {},
"source": [
"To get the remainder, you could subtract off one hour in minutes:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "64b92876",
"metadata": {},
"outputs": [],
"source": [
"remainder = minutes - hours * 60\n",
"remainder"
]
},
{
"cell_type": "markdown",
"id": "05caf27f",
"metadata": {},
"source": [
"Or you could use the **modulus operator**, `%`, which divides two numbers and returns the remainder."
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "0a593844",
"metadata": {},
"outputs": [],
"source": [
"remainder = minutes % 60\n",
"remainder"
]
},
{
"cell_type": "markdown",
"id": "18c1e0d0",
"metadata": {},
"source": [
"The modulus operator is more useful than it might seem.\n",
"For example, it can check whether one number is divisible by another -- if `x % y` is zero, then `x` is divisible by `y`.\n",
"\n",
"Also, it can extract the right-most digit or digits from a number.\n",
"For example, `x % 10` yields the right-most digit of `x` (in base 10).\n",
"Similarly, `x % 100` yields the last two digits."
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "5bd341f7",
"metadata": {},
"outputs": [],
"source": [
"x = 123\n",
"x % 10"
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "367fce0c",
"metadata": {},
"outputs": [],
"source": [
"x % 100"
]
},
{
"cell_type": "markdown",
"id": "f2344fc0",
"metadata": {},
"source": [
"Finally, the modulus operator can do \"clock arithmetic\".\n",
"For example, if an event starts at 11 AM and lasts three hours, we can use the modulus operator to figure out what time it ends.\n",
""
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "db33a44d",
"metadata": {},
"outputs": [],
"source": [
"start = 11\n",
"duration = 3\n",
"end = (start + duration) % 12\n",
"end"
]
},
{
"cell_type": "markdown",
"id": "351c30df",
"metadata": {},
"source": [
"The event would end at 2 PM."
]
},
{
"cell_type": "markdown",
"id": "5ed1b58b",
"metadata": {},
"source": [
"## Boolean Expressions\n",
"\n",
"A **boolean expression** is an expression that is either true or false.\n",
"For example, the following expressions use the equals operator, `==`, which compares two values and produces `True` if they are equal and `False` otherwise:"
]
},
{
"cell_type": "code",
"execution_count": 8,
"id": "85589d38",
"metadata": {},
"outputs": [],
"source": [
"5 == 5"
]
},
{
"cell_type": "code",
"execution_count": 9,
"id": "3c9c8f61",
"metadata": {},
"outputs": [],
"source": [
"5 == 7"
]
},
{
"cell_type": "markdown",
"id": "41fbc642",
"metadata": {},
"source": [
"A common error is to use a single equal sign (`=`) instead of a double equal sign (`==`).\n",
"Remember that `=` assigns a value to a variable and `==` compares two values. "
]
},
{
"cell_type": "code",
"execution_count": 10,
"id": "c0e51bcc",
"metadata": {},
"outputs": [],
"source": [
"x = 5\n",
"y = 7"
]
},
{
"cell_type": "code",
"execution_count": 11,
"id": "a6be44db",
"metadata": {},
"outputs": [],
"source": [
"x == y"
]
},
{
"cell_type": "markdown",
"id": "d3ec6b48",
"metadata": {},
"source": [
"`True` and `False` are special values that belong to the type `bool`;\n",
"they are not strings:"
]
},
{
"cell_type": "code",
"execution_count": 12,
"id": "90fb1c9c",
"metadata": {},
"outputs": [],
"source": [
"type(True)"
]
},
{
"cell_type": "code",
"execution_count": 13,
"id": "c1cae572",
"metadata": {},
"outputs": [],
"source": [
"type(False)"
]
},
{
"cell_type": "markdown",
"id": "451b2e8d",
"metadata": {},
"source": [
"The `==` operator is one of the **relational operators**; the others are:"
]
},
{
"cell_type": "code",
"execution_count": 14,
"id": "c901fe2b",
"metadata": {},
"outputs": [],
"source": [
"x != y # x is not equal to y"
]
},
{
"cell_type": "code",
"execution_count": 15,
"id": "1457949f",
"metadata": {},
"outputs": [],
"source": [
"x > y # x is greater than y"
]
},
{
"cell_type": "code",
"execution_count": 16,
"id": "56bb7eed",
"metadata": {},
"outputs": [],
"source": [
"x < y # x is less than to y"
]
},
{
"cell_type": "code",
"execution_count": 17,
"id": "1cdcc7ab",
"metadata": {},
"outputs": [],
"source": [
"x >= y # x is greater than or equal to y"
]
},
{
"cell_type": "code",
"execution_count": 18,
"id": "df1a1287",
"metadata": {},
"outputs": [],
"source": [
"x <= y # x is less than or equal to y"
]
},
{
"cell_type": "markdown",
"id": "db5a9477",
"metadata": {},
"source": [
"## Logical operators\n",
"\n",
"To combine boolean values into expressions, we can use **logical operators**.\n",
"The most common are `and`, ` or`, and `not`.\n",
"The meaning of these operators is similar to their meaning in English.\n",
"For example, the value of the following expression is `True` only if `x` is greater than `0` *and* less than `10`."
]
},
{
"cell_type": "code",
"execution_count": 19,
"id": "848c5f2c",
"metadata": {},
"outputs": [],
"source": [
"x > 0 and x < 10"
]
},
{
"cell_type": "markdown",
"id": "e8c14026",
"metadata": {},
"source": [
"The following expression is `True` if *either or both* of the conditions is true, that is, if the number is divisible by 2 *or* 3:"
]
},
{
"cell_type": "code",
"execution_count": 20,
"id": "eb66ee6a",
"metadata": {},
"outputs": [],
"source": [
"x % 2 == 0 or x % 3 == 0"
]
},
{
"cell_type": "markdown",
"id": "3bd0ef52",
"metadata": {},
"source": [
"Finally, the `not` operator negates a boolean expression, so the following expression is `True` if `x > y` is `False`."
]
},
{
"cell_type": "code",
"execution_count": 21,
"id": "6de8b97c",
"metadata": {},
"outputs": [],
"source": [
"not x > y"
]
},
{
"cell_type": "markdown",
"id": "fc6098c2",
"metadata": {},
"source": [
"Strictly speaking, the operands of a logical operator should be boolean expressions, but Python is not very strict.\n",
"Any nonzero number is interpreted as `True`:"
]
},
{
"cell_type": "code",
"execution_count": 22,
"id": "add63275",
"metadata": {},
"outputs": [],
"source": [
"42 and True"
]
},
{
"cell_type": "markdown",
"id": "102ceab9",
"metadata": {},
"source": [
"This flexibility can be useful, but there are some subtleties to it that can be confusing.\n",
"You might want to avoid it."
]
},
{
"cell_type": "markdown",
"id": "6b0f2dc1",
"metadata": {},
"source": [
"## if statements\n",
"\n",
"In order to write useful programs, we almost always need the ability to\n",
"check conditions and change the behavior of the program accordingly.\n",
"**Conditional statements** give us this ability. The simplest form is\n",
"the `if` statement:"
]
},
{
"cell_type": "code",
"execution_count": 23,
"id": "80937bef",
"metadata": {},
"outputs": [],
"source": [
"if x > 0:\n",
" print('x is positive')"
]
},
{
"cell_type": "markdown",
"id": "973f705e",
"metadata": {},
"source": [
"`if` is a Python keyword.\n",
"`if` statements have the same structure as function definitions: a\n",
"header followed by an indented statement or sequence of statements called a **block**.\n",
"\n",
"The boolean expression after `if` is called the **condition**.\n",
"If it is true, the statements in the indented block run. If not, they don't.\n",
"\n",
"There is no limit to the number of statements that can appear in the block, but there has to be at least one.\n",
"Occasionally, it is useful to have a block that does nothing -- usually as a place keeper for code you haven't written yet.\n",
"In that case, you can use the `pass` statement, which does nothing."
]
},
{
"cell_type": "code",
"execution_count": 24,
"id": "bc74a318",
"metadata": {},
"outputs": [],
"source": [
"if x < 0:\n",
" pass # TODO: need to handle negative values!"
]
},
{
"cell_type": "markdown",
"id": "adf3f6c5",
"metadata": {},
"source": [
"The word `TODO` in a comment is a conventional reminder that there's something you need to do later."
]
},
{
"cell_type": "markdown",
"id": "eb39bcd9",
"metadata": {},
"source": [
"## The `else` clause\n",
"\n",
"An `if` statement can have a second part, called an `else` clause.\n",
"The syntax looks like this:"
]
},
{
"cell_type": "code",
"execution_count": 25,
"id": "d16f49f2",
"metadata": {},
"outputs": [],
"source": [
"if x % 2 == 0:\n",
" print('x is even')\n",
"else:\n",
" print('x is odd')"
]
},
{
"cell_type": "markdown",
"id": "e7dc8943",
"metadata": {},
"source": [
"If the condition is true, the first indented statement runs; otherwise, the second indented statement runs.\n",
"\n",
"In this example, if `x` is even, the remainder when `x` is divided by `2` is `0`, so the condition is true and the program displays `x is even`.\n",
"If `x` is odd, the remainder is `1`, so the condition\n",
"is false, and the program displays `x is odd`.\n",
"\n",
"Since the condition must be true or false, exactly one of the alternatives will run. \n",
"The alternatives are called **branches**."
]
},
{
"cell_type": "markdown",
"id": "20c8adb6",
"metadata": {},
"source": [
"## Chained conditionals\n",
"\n",
"Sometimes there are more than two possibilities and we need more than two branches.\n",
"One way to express a computation like that is a **chained conditional**, which includes an `elif` clause."
]
},
{
"cell_type": "code",
"execution_count": 26,
"id": "309fccb8",
"metadata": {},
"outputs": [],
"source": [
"if x < y:\n",
" print('x is less than y')\n",
"elif x > y:\n",
" print('x is greater than y')\n",
"else:\n",
" print('x and y are equal')"
]
},
{
"cell_type": "markdown",
"id": "46916379",
"metadata": {},
"source": [
"`elif` is an abbreviation of \"else if\".\n",
"There is no limit on the number of `elif` clauses.\n",
"If there is an `else` clause, it has to be at the end, but there doesn't have to be\n",
"one.\n",
"\n",
"Each condition is checked in order.\n",
"If the first is false, the next is checked, and so on.\n",
"If one of them is true, the corresponding branch runs and the `if` statement ends.\n",
"Even if more than one condition is true, only the first true branch runs."
]
},
{
"cell_type": "markdown",
"id": "e0c0b9dd",
"metadata": {},
"source": [
"## Nested Conditionals\n",
"\n",
"One conditional can also be nested within another.\n",
"We could have written the example in the previous section like this:"
]
},
{
"cell_type": "code",
"execution_count": 27,
"id": "d77539cf",
"metadata": {},
"outputs": [],
"source": [
"if x == y:\n",
" print('x and y are equal')\n",
"else:\n",
" if x < y:\n",
" print('x is less than y')\n",
" else:\n",
" print('x is greater than y')"
]
},
{
"cell_type": "markdown",
"id": "29f67a0a",
"metadata": {},
"source": [
"The outer `if` statement contains two branches. \n",
"The first branch contains a simple statement. The second branch contains another `if` statement, which has two branches of its own.\n",
"Those two branches are both simple statements, although they could have been conditional statements as well.\n",
"\n",
"Although the indentation of the statements makes the structure apparent, **nested conditionals** can be difficult to read.\n",
"I suggest you avoid them when you can.\n",
"\n",
"Logical operators often provide a way to simplify nested conditional statements.\n",
"Here's an example with a nested conditional."
]
},
{
"cell_type": "code",
"execution_count": 28,
"id": "91cac1a0",
"metadata": {},
"outputs": [],
"source": [
"if 0 < x:\n",
" if x < 10:\n",
" print('x is a positive single-digit number.')"
]
},
{
"cell_type": "markdown",
"id": "5292eb11",
"metadata": {},
"source": [
"The `print` statement runs only if we make it past both conditionals, so we get the same effect with the `and` operator."
]
},
{
"cell_type": "code",
"execution_count": 29,
"id": "f8ba1724",
"metadata": {},
"outputs": [],
"source": [
"if 0 < x and x < 10:\n",
" print('x is a positive single-digit number.')"
]
},
{
"cell_type": "markdown",
"id": "dd8e808a",
"metadata": {},
"source": [
"For this kind of condition, Python provides a more concise option:"
]
},
{
"cell_type": "code",
"execution_count": 30,
"id": "014cd6f4",
"metadata": {},
"outputs": [],
"source": [
"if 0 < x < 10:\n",
" print('x is a positive single-digit number.')"
]
},
{
"cell_type": "markdown",
"id": "db583cd9",
"metadata": {},
"source": [
"## Recursion\n",
"\n",
"It is legal for a function to call itself.\n",
"It may not be obvious why that is a good thing, but it turns out to be one of the most magical things a program can do.\n",
"Here's an example.\n",
""
]
},
{
"cell_type": "code",
"execution_count": 31,
"id": "17904e98",
"metadata": {},
"outputs": [],
"source": [
"def countdown(n):\n",
" if n <= 0:\n",
" print('Blastoff!')\n",
" else:\n",
" print(n)\n",
" countdown(n-1)"
]
},
{
"cell_type": "markdown",
"id": "c88e0dc7",
"metadata": {},
"source": [
"If `n` is 0 or negative, `countdown` outputs the word, \"Blastoff!\" Otherwise, it\n",
"outputs `n` and then calls itself, passing `n-1` as an argument.\n",
"\n",
"Here's what happens when we call this function with the argument `3`."
]
},
{
"cell_type": "code",
"execution_count": 32,
"id": "6c1e32e2",
"metadata": {},
"outputs": [],
"source": [
"countdown(3)"
]
},
{
"cell_type": "markdown",
"id": "3f3c87ec",
"metadata": {},
"source": [
"The execution of `countdown` begins with `n=3`, and since `n` is greater\n",
"than `0`, it displays `3`, and then calls itself\\...\n",
"\n",
"> The execution of `countdown` begins with `n=2`, and since `n` is\n",
"> greater than `0`, it displays `2`, and then calls itself\\...\n",
">\n",
"> > The execution of `countdown` begins with `n=1`, and since `n` is\n",
"> > greater than `0`, it displays `1`, and then calls itself\\...\n",
"> >\n",
"> > > The execution of `countdown` begins with `n=0`, and since `n` is\n",
"> > > not greater than `0`, it displays \"Blastoff!\" and returns.\n",
"> >\n",
"> > The `countdown` that got `n=1` returns.\n",
">\n",
"> The `countdown` that got `n=2` returns.\n",
"\n",
"The `countdown` that got `n=3` returns."
]
},
{
"cell_type": "markdown",
"id": "782e95bb",
"metadata": {},
"source": [
"A function that calls itself is **recursive**.\n",
"As another example, we can write a function that prints a string `n` times."
]
},
{
"cell_type": "code",
"execution_count": 33,
"id": "1bb13f8e",
"metadata": {},
"outputs": [],
"source": [
"def print_n_times(string, n):\n",
" if n > 0:\n",
" print(string)\n",
" print_n_times(string, n-1)"
]
},
{
"cell_type": "markdown",
"id": "73d07c17",
"metadata": {},
"source": [
"If `n` is positive, `print_n_times` displays the value of `string` and then calls itself, passing along `string` and `n-1` as arguments.\n",
"\n",
"If `n` is `0` or negative, the condition is false and `print_n_times` does nothing.\n",
"\n",
"Here's how it works."
]
},
{
"cell_type": "code",
"execution_count": 34,
"id": "e7b68c57",
"metadata": {},
"outputs": [],
"source": [
"print_n_times('Spam ', 4)"
]
},
{
"cell_type": "markdown",
"id": "1fb55a78",
"metadata": {},
"source": [
"For simple examples like this, it is probably easier to use a `for`\n",
"loop. But we will see examples later that are hard to write with a `for`\n",
"loop and easy to write with recursion, so it is good to start early."
]
},
{
"cell_type": "markdown",
"id": "c652c739",
"metadata": {},
"source": [
"## Stack diagrams for recursive functions\n",
"\n",
"Here's a stack diagram that shows the frames created when we called `countdown` with `n = 3`."
]
},
{
"cell_type": "code",
"execution_count": 35,
"id": "643148da",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"from diagram import make_frame, Stack\n",
"\n",
"frames = []\n",
"for n in [3,2,1,0]:\n",
" d = dict(n=n)\n",
" frame = make_frame(d, name='countdown', dy=-0.3, loc='left')\n",
" frames.append(frame)\n",
"\n",
"stack = Stack(frames, dy=-0.5)"
]
},
{
"cell_type": "code",
"execution_count": 36,
"id": "a8510119",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"from diagram import diagram, adjust\n",
"\n",
"\n",
"width, height, x, y = [1.74, 2.04, 1.05, 1.77]\n",
"ax = diagram(width, height)\n",
"bbox = stack.draw(ax, x, y)\n",
"# adjust(x, y, bbox)"
]
},
{
"cell_type": "markdown",
"id": "9282331b",
"metadata": {},
"source": [
"The four `countdown` frames have different values for the parameter `n`.\n",
"The bottom of the stack, where `n=0`, is called the **base case**.\n",
"It does not make a recursive call, so there are no more frames."
]
},
{
"cell_type": "code",
"execution_count": 37,
"id": "a2a376b3",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"from diagram import make_frame, Stack\n",
"from diagram import diagram, adjust\n",
"\n",
"frames = []\n",
"for n in [2,1,0]:\n",
" d = dict(string='Hello', n=n)\n",
" frame = make_frame(d, name='print_n_times', dx=1.3, loc='left')\n",
" frames.append(frame)\n",
"\n",
"stack = Stack(frames, dy=-0.5)\n",
"\n",
"width, height, x, y = [3.53, 1.54, 1.54, 1.27]\n",
"ax = diagram(width, height)\n",
"bbox = stack.draw(ax, x, y)\n",
"# adjust(x, y, bbox)"
]
},
{
"cell_type": "markdown",
"id": "37bbc2b8",
"metadata": {},
"source": [
"## Infinite recursion\n",
"\n",
"If a recursion never reaches a base case, it goes on making recursive\n",
"calls forever, and the program never terminates. This is known as\n",
"**infinite recursion**, and it is generally not a good idea.\n",
"Here's a minimal function with an infinite recursion."
]
},
{
"cell_type": "code",
"execution_count": 38,
"id": "af487feb",
"metadata": {},
"outputs": [],
"source": [
"def recurse():\n",
" recurse()"
]
},
{
"cell_type": "markdown",
"id": "450a20ac",
"metadata": {},
"source": [
"Every time `recurse` is called, it calls itself, which creates another frame.\n",
"In Python, there is a limit to the number of frames that can be on the stack at the same time.\n",
"If a program exceeds the limit, it causes a runtime error."
]
},
{
"cell_type": "code",
"execution_count": 39,
"id": "e5d6c732",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"%xmode Context"
]
},
{
"cell_type": "code",
"execution_count": 40,
"id": "22454b51",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"\n",
"recurse()"
]
},
{
"cell_type": "markdown",
"id": "39fc5c31",
"metadata": {},
"source": [
"The traceback indicates that there were almost 3000 frames on the stack when the error occurred.\n",
"\n",
"If you encounter an infinite recursion by accident, review your function to confirm that there is a base case that does not make a recursive call. And if there is a base case, check whether you are guaranteed to reach it."
]
},
{
"cell_type": "markdown",
"id": "45299414",
"metadata": {},
"source": [
"## Keyboard input\n",
"\n",
"The programs we have written so far accept no input from the user. They\n",
"just do the same thing every time.\n",
"\n",
"Python provides a built-in function called `input` that stops the\n",
"program and waits for the user to type something. When the user presses\n",
"*Return* or *Enter*, the program resumes and `input` returns what the user\n",
"typed as a string."
]
},
{
"cell_type": "code",
"execution_count": 41,
"id": "ac0fb4a6",
"metadata": {
"tags": []
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": 42,
"id": "f6a2e4d6",
"metadata": {},
"outputs": [],
"source": [
"text = input()"
]
},
{
"cell_type": "markdown",
"id": "acf9ec53",
"metadata": {},
"source": [
"Before getting input from the user, you might want to display a prompt\n",
"telling the user what to type. `input` can take a prompt as an argument:"
]
},
{
"cell_type": "code",
"execution_count": 43,
"id": "e0600e5e",
"metadata": {
"tags": []
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": 44,
"id": "964346f0",
"metadata": {},
"outputs": [],
"source": [
"name = input('What...is your name?\\n')\n",
"name"
]
},
{
"cell_type": "markdown",
"id": "1b754b39",
"metadata": {},
"source": [
"The sequence `\\n` at the end of the prompt represents a **newline**, which is a special character that causes a line break -- that way the user's input appears below the prompt.\n",
"\n",
"If you expect the user to type an integer, you can use the `int` function to convert the return value to `int`."
]
},
{
"cell_type": "code",
"execution_count": 45,
"id": "590983cd",
"metadata": {
"tags": []
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": 46,
"id": "60a484d7",
"metadata": {},
"outputs": [],
"source": [
"prompt = 'What...is the airspeed velocity of an unladen swallow?\\n'\n",
"speed = input(prompt)\n",
"speed"
]
},
{
"cell_type": "markdown",
"id": "0a65f2af",
"metadata": {},
"source": [
"But if they type something that's not an integer, you'll get a runtime error.\n",
""
]
},
{
"cell_type": "code",
"execution_count": 47,
"id": "8d3d6049",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"%xmode Minimal"
]
},
{
"cell_type": "code",
"execution_count": 48,
"id": "a04e3016",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"\n",
"int(speed)"
]
},
{
"cell_type": "markdown",
"id": "a4ce3ed5",
"metadata": {},
"source": [
"We will see how to handle this kind of error later."
]
},
{
"cell_type": "markdown",
"id": "14c1d3dc",
"metadata": {},
"source": [
"## Debugging\n",
"\n",
"When a syntax or runtime error occurs, the error message contains a lot\n",
"of information, but it can be overwhelming. The most useful parts are\n",
"usually:\n",
"\n",
"- What kind of error it was, and\n",
"\n",
"- Where it occurred.\n",
"\n",
"Syntax errors are usually easy to find, but there are a few gotchas.\n",
"Errors related to spaces and tabs can be tricky because they are invisible\n",
"and we are used to ignoring them."
]
},
{
"cell_type": "code",
"execution_count": 49,
"id": "b82642f6",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"x = 5\n",
" y = 6"
]
},
{
"cell_type": "markdown",
"id": "d1d06263",
"metadata": {},
"source": [
"In this example, the problem is that the second line is indented by one space.\n",
"But the error message points to `y`, which is misleading.\n",
"Error messages indicate where the problem was discovered, but the actual error might be earlier in the code.\n",
"\n",
"The same is true of runtime errors. \n",
"For example, suppose you are trying to convert a ratio to decibels, like this:"
]
},
{
"cell_type": "code",
"execution_count": 50,
"id": "583ef53c",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"%xmode Context"
]
},
{
"cell_type": "code",
"execution_count": 51,
"id": "2f4b6082",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"import math\n",
"numerator = 9\n",
"denominator = 10\n",
"ratio = numerator // denominator\n",
"decibels = 10 * math.log10(ratio)"
]
},
{
"cell_type": "markdown",
"id": "55914374",
"metadata": {},
"source": [
"The error message indicates line 5, but there is nothing wrong with that line.\n",
"The problem is in line 4, which uses integer division instead of floating-point division -- as a result, the value of `ratio` is `0`.\n",
"When we call `math.log10`, we get a `ValueError` with the message `math domain error`, because `0` is not in the \"domain\" of valid arguments for `math.log10`, because the logarithm of `0` is undefined.\n",
"\n",
"In general, you should take the time to read error messages carefully, but don't assume that everything they say is correct."
]
},
{
"cell_type": "markdown",
"id": "8ffe690e",
"metadata": {},
"source": [
"## Glossary\n",
"\n",
"**recursion:**\n",
"The process of calling the function that is currently executing.\n",
"\n",
"**modulus operator:**\n",
"An operator, `%`, that works on integers and returns the remainder when one number is divided by another.\n",
"\n",
"**boolean expression:**\n",
"An expression whose value is either `True` or `False`.\n",
"\n",
"**relational operator:**\n",
"One of the operators that compares its operands: `==`, `!=`, `>`, `<`, `>=`, and `<=`.\n",
"\n",
"**logical operator:**\n",
"One of the operators that combines boolean expressions, including `and`, `or`, and `not`.\n",
"\n",
"**conditional statement:**\n",
"A statement that controls the flow of execution depending on some condition.\n",
"\n",
"**condition:**\n",
"The boolean expression in a conditional statement that determines which branch runs.\n",
"\n",
"**block:**\n",
"One or more statements indented to indicate they are part of another statement.\n",
"\n",
"**branch:**\n",
"One of the alternative sequences of statements in a conditional statement.\n",
"\n",
"**chained conditional:**\n",
"A conditional statement with a series of alternative branches.\n",
"\n",
"**nested conditional:**\n",
"A conditional statement that appears in one of the branches of another conditional statement.\n",
"\n",
"**recursive:**\n",
"A function that calls itself is recursive.\n",
"\n",
"**base case:**\n",
"A conditional branch in a recursive function that does not make a recursive call.\n",
"\n",
"**infinite recursion:**\n",
"A recursion that doesn't have a base case, or never reaches it.\n",
"Eventually, an infinite recursion causes a runtime error.\n",
"\n",
"**newline:**\n",
"A character that creates a line break between two parts of a string."
]
},
{
"cell_type": "markdown",
"id": "841bd256",
"metadata": {},
"source": [
"\n",
"**See also:** the [full vocabulary glossary](https://python.porttack.com/alignment/ap-vocabulary-glossary.html) collects every term in this book, alphabetized, alongside the complete AP CSP exam vocabulary list.\n",
""
]
},
{
"cell_type": "markdown",
"id": "8d783953",
"metadata": {},
"source": [
"## Exercises"
]
},
{
"cell_type": "code",
"execution_count": 52,
"id": "66aae3cb",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"# This cell tells Jupyter to provide detailed debugging information\n",
"# when a runtime error occurs. Run it before working on the exercises.\n",
"\n",
"%xmode Verbose"
]
},
{
"cell_type": "markdown",
"id": "240a3888",
"metadata": {},
"source": [
"### Exercise\n",
"\n",
"The `time` module provides a function, also called `time`, that returns\n",
"returns the number of seconds since the \"Unix epoch\", which is January 1, 1970, 00:00:00 UTC (Coordinated Universal Time)."
]
},
{
"cell_type": "code",
"execution_count": 59,
"id": "1e7a2c07",
"metadata": {},
"outputs": [],
"source": [
"from time import time\n",
"\n",
"now = time()\n",
"now"
]
},
{
"cell_type": "markdown",
"id": "054c3197",
"metadata": {},
"source": [
"Use integer division and the modulus operator to compute the number of days since January 1, 1970 and the current time of day in hours, minutes, and seconds."
]
},
{
"cell_type": "markdown",
"id": "310196ba",
"metadata": {
"tags": []
},
"source": [
"You can read more about the `time` module at ."
]
},
{
"cell_type": "code",
"execution_count": 60,
"id": "c5fa57b2",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": 61,
"id": "322ddd0a",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": 62,
"id": "fc43df7d",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": 63,
"id": "0184d21a",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"id": "6b1fd514",
"metadata": {},
"source": [
"### Exercise\n",
"\n",
"If you are given three sticks, you may or may not be able to arrange\n",
"them in a triangle. For example, if one of the sticks is 12 inches long\n",
"and the other two are one inch long, you will not be able to get the\n",
"short sticks to meet in the middle. For any three lengths, there is a\n",
"test to see if it is possible to form a triangle:\n",
"\n",
"> If any of the three lengths is greater than the sum of the other two,\n",
"> then you cannot form a triangle. Otherwise, you can. (If the sum of\n",
"> two lengths equals the third, they form what is called a \"degenerate\"\n",
"> triangle.)\n",
"\n",
"Write a function named `is_triangle` that takes three integers as\n",
"arguments, and that prints either \"Yes\" or \"No\", depending on\n",
"whether you can or cannot form a triangle from sticks with the given\n",
"lengths. Hint: Use a chained conditional.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 64,
"id": "06381639",
"metadata": {
"tags": []
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"id": "2842401c",
"metadata": {
"tags": []
},
"source": [
"Test your function with the following cases."
]
},
{
"cell_type": "code",
"execution_count": 65,
"id": "156273af",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"is_triangle(4, 5, 6) # should be Yes"
]
},
{
"cell_type": "code",
"execution_count": 66,
"id": "e00793f4",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"is_triangle(1, 2, 3) # should be Yes"
]
},
{
"cell_type": "code",
"execution_count": 67,
"id": "d2911c71",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"is_triangle(6, 2, 3) # should be No"
]
},
{
"cell_type": "code",
"execution_count": 68,
"id": "2b05586e",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"is_triangle(1, 1, 12) # should be No"
]
},
{
"cell_type": "markdown",
"id": "2ba42106",
"metadata": {},
"source": [
"### Exercise\n",
"\n",
"What is the output of the following program? Draw a stack diagram that\n",
"shows the state of the program when it prints the result."
]
},
{
"cell_type": "code",
"execution_count": 69,
"id": "dac374ad",
"metadata": {},
"outputs": [],
"source": [
"def recurse(n, s):\n",
" if n == 0:\n",
" print(s)\n",
" else:\n",
" recurse(n-1, n+s)\n",
"\n",
"recurse(3, 0)"
]
},
{
"cell_type": "code",
"execution_count": 70,
"id": "a438cec5",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": 71,
"id": "2e3f56c7",
"metadata": {
"tags": []
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"id": "bca9517d",
"metadata": {},
"source": [
"### Exercise\n",
"\n",
"The following exercises use the `jupyturtle` module, described in Chapter 4.\n",
"\n",
"Read the following function and see if you can figure out what it does.\n",
"Then run it and see if you got it right.\n",
"Adjust the values of `length`, `angle` and `factor` and see what effect they have on the result."
]
},
{
"cell_type": "markdown",
"id": "ch05-optional-draw",
"metadata": {},
"source": [
"\n",
"*This one is optional -- try it if you have time, but it isn't expected.*\n",
""
]
},
{
"cell_type": "code",
"execution_count": 72,
"id": "2b0d60a1",
"metadata": {},
"outputs": [],
"source": [
"from jupyturtle import forward, left, right, back\n",
"\n",
"def draw(length):\n",
" angle = 50\n",
" factor = 0.6\n",
" \n",
" if length > 5:\n",
" forward(length)\n",
" left(angle)\n",
" draw(factor * length)\n",
" right(2 * angle)\n",
" draw(factor * length)\n",
" left(angle)\n",
" back(length)"
]
},
{
"cell_type": "code",
"execution_count": 73,
"id": "ef0256ee",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"id": "e525ba59",
"metadata": {},
"source": [
"### Exercise\n",
"\n",
"\n",
"A Koch curve is a fractal made by repeating one simple substitution, over and over. Start with a single straight segment. Replace its middle third with two sides of an equilateral triangle -- a small outward bump -- so one segment becomes four shorter ones. Now make that same replacement on each of those four segments, and then on each segment that produces, and so on. The more times you repeat it, the more detailed and jagged the edge becomes, while keeping the same zigzag pattern at every size.\n",
"\n",
"```\n",
"one segment: _____________________\n",
"\n",
"after one substitution: /\\\n",
" ___________ / \\ ___________\n",
"```\n",
"\n",
"The recipe below is exactly that substitution, described recursively: draw a smaller Koch curve, turn, draw another, turn, and so on.\n",
"\n",
"\n",
"To draw a Koch curve with length `x`, all you\n",
"have to do is\n",
"\n",
"1. Draw a Koch curve with length `x/3`.\n",
"\n",
"2. Turn left 60 degrees.\n",
"\n",
"3. Draw a Koch curve with length `x/3`.\n",
"\n",
"4. Turn right 120 degrees.\n",
"\n",
"5. Draw a Koch curve with length `x/3`.\n",
"\n",
"6. Turn left 60 degrees.\n",
"\n",
"7. Draw a Koch curve with length `x/3`.\n",
"\n",
"The exception is if `x` is less than `5` -- in that case, you can just draw a straight line with length `x`.\n",
"\n",
"Write a function called `koch` that takes `x` as an argument and draws a Koch curve with the given length.\n"
]
},
{
"cell_type": "markdown",
"id": "ch05-optional-koch",
"metadata": {},
"source": [
"\n",
"*This one is optional -- try it if you have time, but it isn't expected.*\n",
""
]
},
{
"cell_type": "code",
"execution_count": 74,
"id": "c1acc853",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"id": "2991143a",
"metadata": {},
"source": [
"The result should look like this:"
]
},
{
"cell_type": "code",
"execution_count": 75,
"id": "55507716",
"metadata": {},
"outputs": [],
"source": [
"make_turtle(delay=0)\n",
"koch(120)"
]
},
{
"cell_type": "markdown",
"id": "b1c58420",
"metadata": {
"tags": []
},
"source": [
"Once you have koch working, you can use this loop to draw three Koch curves in the shape of a snowflake."
]
},
{
"cell_type": "code",
"execution_count": 76,
"id": "86d3123b",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"make_turtle(delay=0, height=300)\n",
"for i in range(3):\n",
" koch(120)\n",
" right(120)"
]
},
{
"cell_type": "markdown",
"id": "4c964239",
"metadata": {},
"source": [
"### Exercise\n",
"\n",
"\n",
"A Sierpiński triangle is a fractal made of nested triangles.\n",
"A Sierpiński triangle of degree `0` is a plain equilateral triangle with the given size.\n",
"A Sierpiński triangle of degree `n`, for `n` greater than `0`, is made of three smaller Sierpiński triangles of degree `n-1`, each with half the size, positioned at the three corners of the triangle they replace -- bottom left, bottom right, and top -- leaving a gap where the middle triangle would go.\n",
"\n",
"Write a function called `draw_sierpinski` that takes two parameters, `size` and `degree`, and draws a Sierpiński triangle of that size and degree. Between the three smaller triangles you will need to move the turtle without drawing a line; `penup` and `pendown`, importable from `jupyturtle` the same way you imported `forward`, `left`, `right`, and `back` earlier in this chapter, do that.\n",
""
]
},
{
"cell_type": "markdown",
"id": "ch05-optional-sierpinski",
"metadata": {},
"source": [
"\n",
"*This one is optional -- try it if you have time, but it isn't expected.*\n",
""
]
},
{
"cell_type": "code",
"execution_count": 77,
"id": "68439acf",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"id": "6a95097a",
"metadata": {},
"source": [
"Here's what the result might look like, although the version you get might be different."
]
},
{
"cell_type": "code",
"execution_count": 78,
"id": "43470b3d",
"metadata": {},
"outputs": [],
"source": [
"make_turtle(delay=0, height=200)\n",
"\n",
"draw_sierpinski(100, 3)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "9d6969d4",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"id": "ch05-extra-exercises-intro",
"metadata": {},
"source": [
"\n",
"## Homework\n",
"\n",
"Do either Exercise 1 or Exercise 2, not both. They're interchangeable, so pick whichever appeals to you. Doing both is fine, but the second one earns no additional credit. Required work is five exercises (whichever of 1/2 you pick, plus Exercises 3-6), about 38 minutes total. The time check below must be filled in. The extra credit at the end (a fractal tree or the Collatz sequence) is optional and never substitutes for a required exercise.\n",
"\n",
"Starting this chapter, defining a function without a docstring triggers a warning below that cell -- it isn't graded and won't block anything, but a one-line docstring like the ones from Chapter 4 satisfies it.\n",
"\n",
"Note: the exercises above (elapsed time since the Unix epoch, is_triangle, the stack-diagram prediction, and the three turtle-drawing exercises) are practice. They aren't graded. This is the graded homework.\n",
""
]
},
{
"cell_type": "markdown",
"id": "ch05ex-hw01-heading",
"metadata": {},
"source": [
"\n",
"\n",
"### Exercise 1: letter_grade (do 1 or 2)\n",
"\n",
"Write a function called `letter_grade` that takes a numeric `score` from 0 to 100 and prints the corresponding letter grade: `90` and above is `A`, `80`-`89` is `B`, `70`-`79` is `C`, `60`-`69` is `D`, and below `60` is `F`. Use a chained conditional, the same construct from earlier in this chapter.\n",
""
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ch05ex-hw01-solution",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"id": "ch05ex-hw01-test-note",
"metadata": {},
"source": [
"Test your function with the following cases."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ch05ex-hw01-test1",
"metadata": {},
"outputs": [],
"source": [
"letter_grade(89) # should be B"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ch05ex-hw01-test2",
"metadata": {},
"outputs": [],
"source": [
"letter_grade(90) # should be A"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ch05ex-hw01-test3",
"metadata": {},
"outputs": [],
"source": [
"letter_grade(59) # should be F"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ch05ex-hw01-test4",
"metadata": {},
"outputs": [],
"source": [
"letter_grade(60) # should be D"
]
},
{
"cell_type": "markdown",
"id": "ch05-rps-heading",
"metadata": {},
"source": [
"\n",
"\n",
"### Exercise 2: rps_winner (do 1 or 2)\n",
"\n",
"Write a function called `rps_winner` that takes two strings, `a` and `b`, each one of `'rock'`, `'paper'`, or `'scissors'`, and prints `'a wins'`, `'b wins'`, or `'tie'`. Use a chained conditional with `and`/`or` to check the three matchups where `a` beats `b`.\n",
""
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ch05-rps-solution",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"id": "ch05-rps-test-note",
"metadata": {},
"source": [
"Test your function with the following cases."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ch05-rps-test1",
"metadata": {},
"outputs": [],
"source": [
"rps_winner('rock', 'rock') # should be tie"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ch05-rps-test2",
"metadata": {},
"outputs": [],
"source": [
"rps_winner('rock', 'scissors') # should be a wins"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ch05-rps-test3",
"metadata": {},
"outputs": [],
"source": [
"rps_winner('scissors', 'paper') # should be a wins"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ch05-rps-test4",
"metadata": {},
"outputs": [],
"source": [
"rps_winner('rock', 'paper') # should be b wins"
]
},
{
"cell_type": "markdown",
"id": "ch05ex-hw03-heading",
"metadata": {},
"source": [
"\n",
"\n",
"### Exercise 3: is_leap_year\n",
"\n",
"Write a function called `is_leap_year` that takes a `year` and prints `Yes` or `No`. A year is a leap year if it's divisible by 4, except century years (divisible by 100), which are leap years only if they're also divisible by 400. Use the modulus operator and logical operators.\n",
""
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ch05ex-hw03-solution",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"id": "ch05ex-hw03-test-note",
"metadata": {},
"source": [
"Test your function with the following cases."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ch05ex-hw03-test1",
"metadata": {},
"outputs": [],
"source": [
"is_leap_year(2000) # should be Yes"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ch05ex-hw03-test2",
"metadata": {},
"outputs": [],
"source": [
"is_leap_year(1900) # should be No"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ch05ex-hw03-test3",
"metadata": {},
"outputs": [],
"source": [
"is_leap_year(2024) # should be Yes"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ch05ex-hw03-test4",
"metadata": {},
"outputs": [],
"source": [
"is_leap_year(2023) # should be No"
]
},
{
"cell_type": "markdown",
"id": "ch05ex-hw04-heading",
"metadata": {},
"source": [
"\n",
"\n",
"### Exercise 4: debug countdown_by_two\n",
"\n",
"Here's a function that's supposed to work like `countdown`, but counting down by twos instead of by ones.\n",
""
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ch05ex-hw04-buggy-code",
"metadata": {},
"outputs": [],
"source": [
"def countdown_by_two(n):\n",
" if n == 0:\n",
" print('Blastoff!')\n",
" else:\n",
" print(n)\n",
" countdown_by_two(n-2)"
]
},
{
"cell_type": "markdown",
"id": "ch05ex-hw04-run-note",
"metadata": {},
"source": [
"Run it with a couple of different starting values -- try `countdown_by_two(6)`, then try `countdown_by_two(5)`. One of them behaves fine. The other runs into the same kind of error this chapter covered earlier."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ch05ex-hw04-run-ok",
"metadata": {},
"outputs": [],
"source": [
"countdown_by_two(6)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ch05ex-hw04-xmode",
"metadata": {},
"outputs": [],
"source": [
"%xmode Context"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ch05ex-hw04-run-crash",
"metadata": {},
"outputs": [],
"source": [
"\n",
"countdown_by_two(5)"
]
},
{
"cell_type": "markdown",
"id": "ch05ex-hw04-answer-note",
"metadata": {},
"source": [
"In the markdown cell below, explain what goes wrong with `countdown_by_two` and for which starting values of `n`. Then, in the code cell after that, write a corrected version and test it with a few different starting values, including at least one that would have broken the original."
]
},
{
"cell_type": "markdown",
"id": "ch05ex-hw04-answer-md",
"metadata": {},
"source": [
"*Type your answer here.*"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ch05ex-hw04-answer-code",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"id": "ch05ex-hw05-heading",
"metadata": {},
"source": [
"\n",
"\n",
"### Exercise 5: high-low, one round\n",
"\n",
"Pick a secret number and hard-code it in your solution. Prompt the player with `input()`, convert their guess with `int()`, and print `Too low`, `Too high`, or `Correct!` using a chained conditional. Just one round -- no loop.\n",
""
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ch05ex-hw05-solution",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"id": "ch05ex-hw06-heading",
"metadata": {},
"source": [
"\n",
"\n",
"### Exercise 6: reflection\n",
"\n",
"This chapter showed two ways to handle a problem with several possible outcomes: a chained conditional (`if`/`elif`/`elif`/.../`else`) or nested conditionals (an `if` inside another `if`'s `else`). Which did you reach for more naturally while working through this chapter's exercises, and why?\n",
"\n",
"Answer in the markdown cell below, the same way you did in chap01 through chap04.\n",
""
]
},
{
"cell_type": "markdown",
"id": "ch05ex-hw06-answer",
"metadata": {},
"source": [
"*Type your answer here.*"
]
},
{
"cell_type": "markdown",
"id": "ch05-timecheck-heading",
"metadata": {},
"source": [
"\n",
"\n",
"### Time check\n",
"\n",
"This is graded on being filled in, not on the numbers. There's no right answer, and low numbers don't score better. If this chapter took you three hours, I need to know that. These are estimates: nobody expects you to have timed yourself, so a rough number is exactly what's wanted.\n",
""
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ch05-timecheck-code",
"metadata": {},
"outputs": [],
"source": [
"# Fill this in before you submit. Rough estimates are fine, and low numbers\n",
"# don't score better. Don't count time on the extra credit below.\n",
"# chapter_minutes -> reading the chapter and its practice exercises\n",
"# extra_exercises_minutes -> the six numbered exercises above\n",
"# longest -> which exercise took longest, e.g. 1\n",
"chapter_minutes = 0\n",
"extra_exercises_minutes = 0\n",
"longest = 0\n",
"\n",
"from working_in_python import time_check\n",
"time_check(chapter_minutes, extra_exercises_minutes, longest)"
]
},
{
"cell_type": "markdown",
"id": "ch05-extra-credit-intro",
"metadata": {},
"source": [
"\n",
"## Extra credit: two ways to recurse\n",
"\n",
"Do either the fractal tree or the Collatz sequence below, not both. They're interchangeable, so pick whichever appeals to you. Doing both is fine, but the second one earns no additional credit. Neither substitutes for a required exercise. This is worth 0.5 points.\n",
"\n",
"If you'd like to watch recursion draw something first, the koch/snowflake cells above (optional practice) are worth running if you haven't already -- this notebook ships with no saved output, so nothing renders until you run the cells yourself.\n",
""
]
},
{
"cell_type": "markdown",
"id": "ch05-tree-heading",
"metadata": {},
"source": [
"\n",
"\n",
"### Fractal tree (extra credit -- do this one OR Collatz, not both)\n",
"\n",
"Write a function called `tree` that takes `length` as a parameter and draws a fractal tree: go forward, turn left and recurse on a shorter branch, turn right twice and recurse on another shorter branch of the same length, then turn back and return to where you started -- the same shape as the `draw` function earlier in this chapter, but written as its own function with a clear base case (stop recursing once the branch gets too short to matter).\n",
"\n",
"Once `tree` works, generalize it the way Chapter 4 generalized `circle` into `arc`: add `angle` and `factor` parameters so the branch angle and the shrink factor per level aren't hardcoded. Pick your own values for all three and try a few combinations.\n",
""
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ch05-tree-solution",
"metadata": {},
"outputs": [],
"source": [
"make_turtle()\n",
"# Solution goes here"
]
},
{
"cell_type": "markdown",
"id": "ch05-tree-demo-note",
"metadata": {},
"source": [
"Here's what the result might look like, though yours will depend on the angle and shrink factor you picked."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ch05-tree-demo",
"metadata": {},
"outputs": [],
"source": [
"make_turtle(delay=0)\n",
"tree(length=80, angle=30, factor=0.7)"
]
},
{
"cell_type": "markdown",
"id": "ch05-collatz-heading",
"metadata": {},
"source": [
"\n",
"\n",
"### Collatz (extra credit -- do this one OR the fractal tree, not both)\n",
"\n",
"The Collatz conjecture starts from any positive integer `n`. If `n` is even, the next number is `n // 2`. If `n` is odd, the next number is `3 * n + 1`. Repeat, and every starting value anyone has ever tried eventually reaches 1 -- though no one has proved that it always must.\n",
"\n",
"Write a recursive function called `collatz` that takes a positive integer `n`, prints it, and then calls itself with the next number in the sequence. Once `n` reaches 1, print it and stop -- don't recurse past it. Test your function with a few different starting values, including at least one that takes many steps to reach 1.\n",
""
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ch05-collatz-solution",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"id": "ch05-copy-heading",
"metadata": {},
"source": [
"\n",
"### Finished? Copy your work\n",
"\n",
"This isn't part of Exercise 6. It's a tool. Run the cell below to copy this notebook (including anything you've run) so you can paste it into a document.\n",
""
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ch05-copy-button",
"metadata": {},
"outputs": [],
"source": [
"working_in_python.show_copy_notebook_button()"
]
},
{
"cell_type": "markdown",
"id": "a7f4edf8",
"metadata": {
"tags": []
},
"source": [
"\n",
"---\n",
"\n",
"**Working in Python** — modified by Eric Brown for a high school Computer Science Principles class. Source and modifications: [github.com/porttack/working-in-python](https://github.com/porttack/working-in-python)\n",
"\n",
"---\n",
"\n",
"\n",
"[Think Python: 3rd Edition](https://allendowney.github.io/ThinkPython/index.html)\n",
"\n",
"Copyright 2024 [Allen B. Downey](https://allendowney.com)\n",
"\n",
"Code license: [MIT License](https://mit-license.org/)\n",
"\n",
"Text license: [Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-nc-sa/4.0/)\n",
"\n",
"\n",
"---\n",
"\n",
"## Standards alignment\n",
"\n",
"**AP CSP:** [3.5 Boolean Expressions](https://python.porttack.com/alignment/apcsp-standards-reference.html#T-3.5) and [3.6 Conditionals](https://python.porttack.com/alignment/apcsp-standards-reference.html#T-3.6) (Big Idea 3, 30–35% of the exam). Also [3.7 Nested Conditionals](https://python.porttack.com/alignment/apcsp-standards-reference.html#T-3.7), [1.2 Program Function and Purpose](https://python.porttack.com/alignment/apcsp-standards-reference.html#T-1.2), and [1.4 Identifying and Correcting Errors](https://python.porttack.com/alignment/apcsp-standards-reference.html#T-1.4) (Big Idea 1, 10–13%), headers only.\n",
"**California 9-12:** [9-12.AP.14](https://python.porttack.com/alignment/ca-cs-standards-reference.html#S-9-12.AP.14)\n",
"**CSTA 2026:** [HS-PRO-RD-17](https://python.porttack.com/alignment/csta2026-standards-reference.html#T-HS-PRO-RD-17), [HS-ALG-PS-02](https://python.porttack.com/alignment/csta2026-standards-reference.html#T-HS-ALG-PS-02). Also [HS-ALG-PS-03](https://python.porttack.com/alignment/csta2026-standards-reference.html#T-HS-ALG-PS-03), headers only.\n",
"**CA CTE (ICT):** [C4.9](https://python.porttack.com/alignment/ca-ict-anchor-standards-reference.html#T-C4.9) (Pathway C), [5.12](https://python.porttack.com/alignment/ca-ict-anchor-standards-reference.html#T-5.12), [5.9](https://python.porttack.com/alignment/ca-ict-anchor-standards-reference.html#T-5.9) (Anchor Standards). Also [5.5](https://python.porttack.com/alignment/ca-ict-anchor-standards-reference.html#T-5.5) and [C5.6](https://python.porttack.com/alignment/ca-ict-anchor-standards-reference.html#T-C5.6), headers only.\n",
"\n",
"This chapter's boolean expressions and `if` statements are 3.5 and 3.6 directly, and California's AP.14 anchors recursion here to chapter 6's Fibonacci comparison. Nested conditionals get the same secondary treatment the text itself gives them — the book shows logical operators replacing them, not the other way around, which is CSTA's own reworked-for-clarity standard. Recursion has no pseudocode form on the exam, but it is exactly CTE's \"function that calls itself,\" and the chapter's debugging section traces symptoms back to their real cause rather than guessing.\n",
"\n",
"**Vocabulary:** this book writes the modulus operator as `%`. The exam writes `MOD`.\n",
""
]
}
],
"metadata": {
"celltoolbar": "Tags",
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.10.11"
}
},
"nbformat": 4,
"nbformat_minor": 5
}