chapters/chap06.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "1331faa1",
   "metadata": {},
   "source": [
    "You can order print and ebook versions of *Think Python 3e* from\n",
    "[Bookshop.org](https://bookshop.org/a/98697/9781098155438) and\n",
    "[Amazon](https://www.amazon.com/_/dp/1098155432?smid=ATVPDKIKX0DER&_encoding=UTF8&tag=oreilly20-20&_encoding=UTF8&tag=greenteapre01-20&linkCode=ur2&linkId=e2a529f94920295d27ec8a06e757dc7c&camp=1789&creative=9325)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "id": "56b1c184",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from os.path import basename, exists\n",
    "\n",
    "def download(url):\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/AllenDowney/ThinkPython/raw/v3/thinkpython.py');\n",
    "download('https://github.com/AllenDowney/ThinkPython/raw/v3/diagram.py');\n",
    "\n",
    "import thinkpython"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "88ecc443",
   "metadata": {},
   "source": [
    "# Return Values\n",
    "\n",
    "In previous chapters, we've used built-in functions -- like `abs` and `round` -- and functions in the math module -- like `sqrt` and `pow`.\n",
    "When you call one of these functions, it returns a value you can assign to a variable or use as part of an expression.\n",
    "\n",
    "The functions we have written so far are different.\n",
    "Some use the `print` function to display values, and some use turtle functions to draw figures.\n",
    "But they don't return values we assign to variables or use in expressions.\n",
    "\n",
    "In this chapter, we'll see how to write functions that return values."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6cf2cf80",
   "metadata": {},
   "source": [
    "## Some functions have return values\n",
    "\n",
    "When you call a function like `math.sqrt`, the result is called a **return value**.\n",
    "If the function call appears at the end of a cell, Jupyter displays the return value immediately."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "id": "e0e1dd91",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "math.sqrt(42 / math.pi)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4b4885c2",
   "metadata": {},
   "source": [
    "If you assign the return value to a variable, it doesn't get displayed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "id": "5aaf62d2",
   "metadata": {},
   "outputs": [],
   "source": [
    "radius = math.sqrt(42 / math.pi)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "196c692b",
   "metadata": {},
   "source": [
    "But you can display it later."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "id": "741f7386",
   "metadata": {},
   "outputs": [],
   "source": [
    "radius"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "257b28d5",
   "metadata": {},
   "source": [
    "Or you can use the return value as part of an expression."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "id": "e56d39c4",
   "metadata": {},
   "outputs": [],
   "source": [
    "radius + math.sqrt(42 / math.pi)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "23ed47ab",
   "metadata": {},
   "source": [
    "Here's an example of a function that returns a value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "id": "50a9a9be",
   "metadata": {},
   "outputs": [],
   "source": [
    "def circle_area(radius):\n",
    "    area = math.pi * radius**2\n",
    "    return area"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "273acabc",
   "metadata": {},
   "source": [
    "`circle_area` takes `radius` as a parameter and computes the area of a circle with that radius.\n",
    "\n",
    "The last line is a `return` statement that returns the value of `area`.\n",
    "\n",
    "If we call the function like this, Jupyter displays the return value.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "id": "d70fd9b5",
   "metadata": {},
   "outputs": [],
   "source": [
    "circle_area(radius)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4f28bfd6",
   "metadata": {},
   "source": [
    "We can assign the return value to a variable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "id": "ef20ba8c",
   "metadata": {},
   "outputs": [],
   "source": [
    "a = circle_area(radius)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3f82fe70",
   "metadata": {},
   "source": [
    "Or use it as part of an expression."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "id": "0a4670f4",
   "metadata": {},
   "outputs": [],
   "source": [
    "circle_area(radius) + 2 * circle_area(radius / 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "15122fd2",
   "metadata": {},
   "source": [
    "Later we can display the value of the variable we assigned the result to."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "id": "6e6460b9",
   "metadata": {},
   "outputs": [],
   "source": [
    "a"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a3f6dcae",
   "metadata": {},
   "source": [
    "But we can't access `area`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "id": "77613df9",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "%%expect NameError\n",
    "\n",
    "area"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f8ace9ce",
   "metadata": {},
   "source": [
    "`area` is a local variable in a function, so we can't access it from outside the function."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "41a4f03f",
   "metadata": {},
   "source": [
    "## And some have None\n",
    "\n",
    "If a function doesn't have a `return` statement, it returns `None`, which is a special value like `True` and `False`.\n",
    "For example, here's the `repeat` function from Chapter 3."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "id": "89c083f8",
   "metadata": {},
   "outputs": [],
   "source": [
    "def repeat(word, n):\n",
    "    print(word * n)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6ada19cf",
   "metadata": {},
   "source": [
    "If we call it like this, it displays the first line of the Monty Python song \"Finland\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "id": "737b67ca",
   "metadata": {},
   "outputs": [],
   "source": [
    "repeat('Finland, ', 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fe49f5e5",
   "metadata": {},
   "source": [
    "This function uses the `print` function to display a string, but it does not use a `return` statement to return a value.\n",
    "If we assign the result to a variable, it displays the string anyway. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "id": "9b4fa14f",
   "metadata": {},
   "outputs": [],
   "source": [
    "result = repeat('Finland, ', 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4ecabbdb",
   "metadata": {},
   "source": [
    "And if we display the value of the variable, we get nothing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "id": "50f96bcb",
   "metadata": {},
   "outputs": [],
   "source": [
    "result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "07033959",
   "metadata": {},
   "source": [
    "`result` actually has a value, but Jupyter doesn't show it.\n",
    "However, we can display it like this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "id": "6712f2df",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "379b98c5",
   "metadata": {},
   "source": [
    "The return value from `repeat` is `None`.\n",
    "\n",
    "Now here's a function similar to `repeat` except that has a return value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "id": "0ec1afd3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def repeat_string(word, n):\n",
    "    return word * n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "db6ad3d4",
   "metadata": {},
   "source": [
    "Notice that we can use an expression in a `return` statement, not just a variable.\n",
    "\n",
    "With this version, we can assign the result to a variable.\n",
    "When the function runs, it doesn't display anything."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "id": "c82334b6",
   "metadata": {},
   "outputs": [],
   "source": [
    "line = repeat_string('Spam, ', 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1232cd8a",
   "metadata": {},
   "source": [
    "But later we can display the value assigned to `line`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "id": "595ec598",
   "metadata": {},
   "outputs": [],
   "source": [
    "line"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ae02c7d2",
   "metadata": {},
   "source": [
    "A function like this is called a **pure function** because it doesn't display anything or have any other effect -- other than returning a value."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "567ae734",
   "metadata": {},
   "source": [
    "## Return values and conditionals\n",
    "\n",
    "If Python did not provide `abs`, we could write it like this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "id": "236c59e6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def absolute_value(x):\n",
    "    if x < 0:\n",
    "        return -x\n",
    "    else:\n",
    "        return x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ffd559b8",
   "metadata": {},
   "source": [
    "If `x` is negative, the first `return` statement returns `-x` and the function ends immediately.\n",
    "Otherwise, the second `return` statement returns `x` and the function ends.\n",
    "So this function is correct.\n",
    "\n",
    "However, if you put `return` statements in a conditional, you have to make sure that every possible path through the program hits a `return` statement.\n",
    "For example, here's an incorrect version of `absolute_value`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "id": "2f60639c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def absolute_value_wrong(x):\n",
    "    if x < 0:\n",
    "        return -x\n",
    "    if x > 0:\n",
    "        return x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "da3280ae",
   "metadata": {},
   "source": [
    "Here's what happens if we call this function with `0` as an argument."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "id": "c9dae6c8",
   "metadata": {},
   "outputs": [],
   "source": [
    "absolute_value_wrong(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5733f239",
   "metadata": {},
   "source": [
    "We get nothing! Here's the problem: when `x` is `0`, neither condition is true, and the function ends without hitting a `return` statement, which means that the return value is `None`, so Jupyter displays nothing.\n",
    "\n",
    "As another example, here's a version of `absolute_value` with an extra `return` statement at the end."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "id": "c8c4edee",
   "metadata": {},
   "outputs": [],
   "source": [
    "def absolute_value_extra_return(x):\n",
    "    if x < 0:\n",
    "        return -x\n",
    "    else:\n",
    "        return x\n",
    "    \n",
    "    return 'This is dead code'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cf5486fd",
   "metadata": {},
   "source": [
    "If `x` is negative, the first `return` statement runs and the function ends.\n",
    "Otherwise the second `return` statement runs and the function ends.\n",
    "Either way, we never get to the third `return` statement -- so it can never run.\n",
    "\n",
    "Code that can never run is called **dead code**.\n",
    "In general, dead code doesn't do any harm, but it often indicates a misunderstanding, and it might be confusing to someone trying to understand the program."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "68a6ae39",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Incremental development\n",
    "\n",
    "As you write larger functions, you might find yourself spending more\n",
    "time debugging.\n",
    "To deal with increasingly complex programs, you might want to try **incremental development**, which is a way of adding and testing only a small amount of code at a time.\n",
    "\n",
    "As an example, suppose you want to find the distance between two points represented by the coordinates $(x_1, y_1)$ and $(x_2, y_2)$.\n",
    "By the Pythagorean theorem, the distance is:\n",
    "\n",
    "$$\\mathrm{distance} = \\sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$$ \n",
    "\n",
    "The first step is to consider what a `distance` function should look like in Python -- that is, what are the inputs (parameters) and what is the output (return value)?\n",
    "\n",
    "For this function, the inputs are the coordinates of the points.\n",
    "The return value is the distance.\n",
    "Immediately you can write an outline of the function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "id": "bbcab1ed",
   "metadata": {},
   "outputs": [],
   "source": [
    "def distance(x1, y1, x2, y2):\n",
    "    return 0.0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b384fcf",
   "metadata": {},
   "source": [
    "This version doesn't compute distances yet -- it always returns zero.\n",
    "But it is a complete function with a return value, which means that you can test it before you make it more complicated.\n",
    "\n",
    "To test the new function, we'll call it with sample arguments:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "id": "923d96db",
   "metadata": {},
   "outputs": [],
   "source": [
    "distance(1, 2, 4, 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "13a98096",
   "metadata": {},
   "source": [
    "I chose these values so that the horizontal distance is `3` and the\n",
    "vertical distance is `4`.\n",
    "That way, the result is `5`, the hypotenuse of a `3-4-5` right triangle. When testing a function, it is useful to know the right answer.\n",
    "\n",
    "At this point we have confirmed that the function runs and returns a value, and we can start adding code to the body.\n",
    "A good next step is to find the differences `x2 - x1` and `y2 - y1`. \n",
    "Here's a version that stores those values in temporary variables and displays them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "id": "9374cfe3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def distance(x1, y1, x2, y2):\n",
    "    dx = x2 - x1\n",
    "    dy = y2 - y1\n",
    "    print('dx is', dx)\n",
    "    print('dy is', dy)\n",
    "    return 0.0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c342a3bd",
   "metadata": {},
   "source": [
    "If the function is working, it should display `dx is 3` and `dy is 4`.\n",
    "If so, we know that the function is getting the right arguments and\n",
    "performing the first computation correctly. If not, there are only a few\n",
    "lines to check."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "id": "405af839",
   "metadata": {},
   "outputs": [],
   "source": [
    "distance(1, 2, 4, 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9424eca9",
   "metadata": {},
   "source": [
    "Good so far. Next we compute the sum of squares of `dx` and `dy`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "id": "e52b3b04",
   "metadata": {},
   "outputs": [],
   "source": [
    "def distance(x1, y1, x2, y2):\n",
    "    dx = x2 - x1\n",
    "    dy = y2 - y1\n",
    "    dsquared = dx**2 + dy**2\n",
    "    print('dsquared is: ', dsquared)\n",
    "    return 0.0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e28262f9",
   "metadata": {},
   "source": [
    "Again, we can run the function and check the output, which should be `25`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "id": "38eebbf3",
   "metadata": {},
   "outputs": [],
   "source": [
    "distance(1, 2, 4, 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c09f0ddc",
   "metadata": {},
   "source": [
    "Finally, we can use `math.sqrt` to compute the distance:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "id": "b4536ea0",
   "metadata": {},
   "outputs": [],
   "source": [
    "def distance(x1, y1, x2, y2):\n",
    "    dx = x2 - x1\n",
    "    dy = y2 - y1\n",
    "    dsquared = dx**2 + dy**2\n",
    "    result = math.sqrt(dsquared)\n",
    "    print(\"result is\", result)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f27902ac",
   "metadata": {},
   "source": [
    "And test it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "id": "325efb93",
   "metadata": {},
   "outputs": [],
   "source": [
    "distance(1, 2, 4, 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ad2e626",
   "metadata": {},
   "source": [
    "The result is correct, but this version of the function displays the result rather than returning it, so the return value is `None`.\n",
    "\n",
    "We can fix that by replacing the `print` function with a `return` statement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "id": "3cd982ce",
   "metadata": {},
   "outputs": [],
   "source": [
    "def distance(x1, y1, x2, y2):\n",
    "    dx = x2 - x1\n",
    "    dy = y2 - y1\n",
    "    dsquared = dx**2 + dy**2\n",
    "    result = math.sqrt(dsquared)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f3a13a14",
   "metadata": {},
   "source": [
    "This version of `distance` is a pure function.\n",
    "If we call it like this, only the result is displayed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "id": "c734f5b2",
   "metadata": {},
   "outputs": [],
   "source": [
    "distance(1, 2, 4, 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7db8cf86",
   "metadata": {},
   "source": [
    "And if we assign the result to a variable, nothing is displayed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "id": "094a242f",
   "metadata": {},
   "outputs": [],
   "source": [
    "d = distance(1, 2, 4, 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c3b8829",
   "metadata": {},
   "source": [
    "The `print` statements we wrote are useful for debugging, but once the function is working, we can remove them. \n",
    "Code like that is called **scaffolding** because it is helpful for building the program but is not part of the final product.\n",
    "\n",
    "This example demonstrates incremental development.\n",
    "The key aspects of this process are:\n",
    "\n",
    "1.  Start with a working program, make small changes, and test after every change.\n",
    "\n",
    "2.  Use variables to hold intermediate values so you can display and check them.\n",
    "\n",
    "3.  Once the program is working, remove the scaffolding.\n",
    "\n",
    "At any point, if there is an error, you should have a good idea where it is.\n",
    "Incremental development can save you a lot of debugging time."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3dd7514f",
   "metadata": {},
   "source": [
    "## Boolean functions\n",
    "\n",
    "Functions can return the boolean values `True` and `False`, which is often convenient for encapsulating a complex test in a function.\n",
    "For example, `is_divisible` checks whether `x` is divisible by `y` with no remainder."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "id": "64207948",
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_divisible(x, y):\n",
    "    if x % y == 0:\n",
    "        return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f3a58afb",
   "metadata": {},
   "source": [
    "Here's how we use it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "id": "c367cdae",
   "metadata": {},
   "outputs": [],
   "source": [
    "is_divisible(6, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "id": "837f4f95",
   "metadata": {},
   "outputs": [],
   "source": [
    "is_divisible(6, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e9103ece",
   "metadata": {},
   "source": [
    "Inside the function, the result of the `==` operator is a boolean, so we can write the\n",
    "function more concisely by returning it directly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "id": "e411354f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_divisible(x, y):\n",
    "    return x % y == 0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4d82dae5",
   "metadata": {},
   "source": [
    "Boolean functions are often used in conditional statements."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "id": "925e7d4f",
   "metadata": {},
   "outputs": [],
   "source": [
    "if is_divisible(6, 2):\n",
    "    print('divisible')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9e232afc",
   "metadata": {},
   "source": [
    "It might be tempting to write something like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 126,
   "id": "62178e75",
   "metadata": {},
   "outputs": [],
   "source": [
    "if is_divisible(6, 2) == True:\n",
    "    print('divisible')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ff9e5160",
   "metadata": {},
   "source": [
    "But the comparison is unnecessary."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a932a966",
   "metadata": {},
   "source": [
    "## Recursion with return values\n",
    "\n",
    "Now that we can write functions with return values, we can write recursive functions with return values, and with that capability, we have passed an important threshold -- the subset of Python we have is now **Turing complete**, which means that we can perform any computation that can be described by an algorithm.\n",
    "\n",
    "To demonstrate recursion with return values, we'll evaluate a few recursively defined mathematical functions.\n",
    "A recursive definition is similar to a circular definition, in the sense that the definition refers to the thing being defined. A truly circular definition is not very useful:\n",
    "\n",
    "> vorpal: An adjective used to describe something that is vorpal.\n",
    "\n",
    "If you saw that definition in the dictionary, you might be annoyed. \n",
    "On the other hand, if you looked up the definition of the factorial function, denoted with the symbol $!$, you might get something like this: \n",
    "\n",
    "$$\\begin{aligned}\n",
    "0! &= 1 \\\\\n",
    "n! &= n~(n-1)!\n",
    "\\end{aligned}$$ \n",
    "\n",
    "This definition says that the factorial of $0$ is $1$, and the factorial of any other value, $n$, is $n$ multiplied by the factorial of $n-1$.\n",
    "\n",
    "If you can write a recursive definition of something, you can write a Python program to evaluate it. \n",
    "Following an incremental development process, we'll start with a function that take `n` as a parameter and always returns `0`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "id": "23e37c79",
   "metadata": {},
   "outputs": [],
   "source": [
    "def factorial(n):\n",
    "    return 0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ee1f63b8",
   "metadata": {},
   "source": [
    "Now let's add the first part of the definition -- if the argument happens to be `0`, all we have to do is return `1`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "id": "5ea57d9f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def factorial(n):\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    else:\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4f2fd7c7",
   "metadata": {},
   "source": [
    "Now let's fill in the second part -- if `n` is not `0`, we have to make a recursive\n",
    "call to find the factorial of `n-1` and then multiply the result by `n`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "id": "b66e670b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def factorial(n):\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    else:\n",
    "        recurse = factorial(n-1)\n",
    "        return n * recurse"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "da3d1595",
   "metadata": {},
   "source": [
    "The flow of execution for this program is similar to the flow of `countdown` in Chapter 5.\n",
    "If we call `factorial` with the value `3`:\n",
    "\n",
    "Since `3` is not `0`, we take the second branch and calculate the factorial\n",
    "of `n-1`\\...\n",
    "\n",
    "> Since `2` is not `0`, we take the second branch and calculate the\n",
    "> factorial of `n-1`\\...\n",
    ">\n",
    "> > Since `1` is not `0`, we take the second branch and calculate the\n",
    "> > factorial of `n-1`\\...\n",
    "> >\n",
    "> > > Since `0` equals `0`, we take the first branch and return `1` without\n",
    "> > > making any more recursive calls.\n",
    "> >\n",
    "> > The return value, `1`, is multiplied by `n`, which is `1`, and the\n",
    "> > result is returned.\n",
    ">\n",
    "> The return value, `1`, is multiplied by `n`, which is `2`, and the result\n",
    "> is returned.\n",
    "\n",
    "The return value `2` is multiplied by `n`, which is `3`, and the result,\n",
    "`6`, becomes the return value of the function call that started the whole\n",
    "process.\n",
    "\n",
    "The following figure shows the stack diagram for this sequence of function calls."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "id": "455f0457",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from diagram import Frame, Stack, make_binding\n",
    "\n",
    "main = Frame([], name='__main__', loc='left')\n",
    "frames = [main]\n",
    "\n",
    "ns = 3, 2, 1\n",
    "recurses = 2, 1, 1\n",
    "results = 6, 2, 1\n",
    "\n",
    "for n, recurse, result in zip(ns, recurses, results):\n",
    "    binding1 = make_binding('n', n)\n",
    "    binding2 = make_binding('recurse', recurse)\n",
    "    frame = Frame([binding1, binding2], \n",
    "                  name='factorial', value=result,\n",
    "                  loc='left', dx=1.2)\n",
    "    frames.append(frame)\n",
    "    \n",
    "binding1 = make_binding('n', n)\n",
    "frame = Frame([binding1], name='factorial', value=1, \n",
    "              shim=1.2, loc='left', dx=1.4)\n",
    "frames.append(frame)\n",
    "\n",
    "stack = Stack(frames, dy=-0.45)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "id": "a75ccd9b",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from diagram import diagram, adjust\n",
    "\n",
    "width, height, x, y = [2.74, 2.26, 0.73, 2.05]\n",
    "ax = diagram(width, height)\n",
    "bbox = stack.draw(ax, x, y)\n",
    "# adjust(x, y, bbox)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f924c539",
   "metadata": {},
   "source": [
    "The return values are shown being passed back up the stack.\n",
    "In each frame, the return value is the product of `n` and `recurse`.\n",
    "\n",
    "In the last frame, the local variable `recurse` does not exist because the branch that creates it does not run."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "acea9dc1",
   "metadata": {},
   "source": [
    "## Leap of faith\n",
    "\n",
    "Following the flow of execution is one way to read programs, but it can quickly become overwhelming. An alternative is what I call the \"leap of faith\". When you come to a function call, instead of following the flow of execution, you *assume* that the function works correctly and returns the right result.\n",
    "\n",
    "In fact, you are already practicing this leap of faith when you use built-in functions.\n",
    "When you call `abs` or `math.sqrt`, you don't examine the bodies of those functions -- you just assume that they work.\n",
    "\n",
    "The same is true when you call one of your own functions. For example, earlier we wrote a function called `is_divisible` that determines whether one number is divisible by another. Once we convince ourselves that this function is correct, we can use it without looking at the body again.\n",
    "\n",
    "The same is true of recursive programs.\n",
    "When you get to the recursive call, instead of following the flow of execution, you should assume that the recursive call works and then ask yourself, \"Assuming that I can compute the factorial of $n-1$, can I compute the factorial of $n$?\"\n",
    "The recursive definition of factorial implies that you can, by multiplying by $n$.\n",
    "\n",
    "Of course, it's a bit strange to assume that the function works correctly when you haven't finished writing it, but that's why it's called a leap of faith!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ca2a2d76",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Fibonacci\n",
    "\n",
    "After `factorial`, the most common example of a recursive function is `fibonacci`, which has the following definition: \n",
    "\n",
    "$$\\begin{aligned}\n",
    "\\mathrm{fibonacci}(0) &= 0 \\\\\n",
    "\\mathrm{fibonacci}(1) &= 1 \\\\\n",
    "\\mathrm{fibonacci}(n) &= \\mathrm{fibonacci}(n-1) + \\mathrm{fibonacci}(n-2)\n",
    "\\end{aligned}$$ \n",
    "\n",
    "Translated into Python, it looks like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "id": "cad75752",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fibonacci(n):\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    elif  n == 1:\n",
    "        return 1\n",
    "    else:\n",
    "        return fibonacci(n-1) + fibonacci(n-2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "69d56a0b",
   "metadata": {},
   "source": [
    "If you try to follow the flow of execution here, even for small values of $n$, your head explodes.\n",
    "But according to the leap of faith, if you assume that the two recursive calls work correctly, you can be confident that the last `return` statement is correct.\n",
    "\n",
    "As an aside, this way of computing Fibonacci numbers is very inefficient.\n",
    "In [Chapter 10](section_memos) I'll explain why and suggest a way to improve it."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "26d9706b",
   "metadata": {},
   "source": [
    "## Checking types\n",
    "\n",
    "What happens if we call `factorial` and give it `1.5` as an argument?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "id": "5e4b5f1d",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "%%expect RecursionError\n",
    "\n",
    "factorial(1.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0bec7ba4",
   "metadata": {},
   "source": [
    "It looks like an infinite recursion. How can that be? The function has a\n",
    "base case -- when `n == 0`.\n",
    "But if `n` is not an integer, we can *miss* the base case and recurse forever.\n",
    "\n",
    "In this example, the initial value of `n` is `1.5`.\n",
    "In the first recursive call, the value of `n` is `0.5`.\n",
    "In the next, it is `-0.5`. \n",
    "From there, it gets smaller (more negative), but it will never be `0`.\n",
    "\n",
    "To avoid infinite recursion we can use the built-in function `isinstance` to check the type of the argument.\n",
    "Here's how we check whether a value is an integer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 134,
   "id": "3f607dff",
   "metadata": {},
   "outputs": [],
   "source": [
    "isinstance(3, int)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 135,
   "id": "ab638bfe",
   "metadata": {},
   "outputs": [],
   "source": [
    "isinstance(1.5, int)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b0017b42",
   "metadata": {},
   "source": [
    "Now here's a version of `factorial` with error-checking."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 136,
   "id": "73aafac0",
   "metadata": {},
   "outputs": [],
   "source": [
    "def factorial(n):\n",
    "    if not isinstance(n, int):\n",
    "        print('factorial is only defined for integers.')\n",
    "        return None\n",
    "    elif n < 0:\n",
    "        print('factorial is not defined for negative numbers.')\n",
    "        return None\n",
    "    elif n == 0:\n",
    "        return 1\n",
    "    else:\n",
    "        return n * factorial(n-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0561e3f5",
   "metadata": {},
   "source": [
    "First it checks whether `n` is an integer.\n",
    "If not, it displays an error message and returns `None`.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "id": "be881cb7",
   "metadata": {},
   "outputs": [],
   "source": [
    "factorial('crunchy frog')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "10b00a39",
   "metadata": {},
   "source": [
    "Then it checks whether `n` is negative.\n",
    "If so, it displays an error message and returns `None.`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "id": "fa83014f",
   "metadata": {},
   "outputs": [],
   "source": [
    "factorial(-2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "96aa1403",
   "metadata": {},
   "source": [
    "If we get past both checks, we know that `n` is a non-negative integer, so we can be confident the recursion will terminate.\n",
    "Checking the parameters of a function to make sure they have the correct types and values is called **input validation**."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eb8a85a7",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Debugging\n",
    "\n",
    "Breaking a large program into smaller functions creates natural checkpoints for debugging.\n",
    "If a function is not working, there are three possibilities to consider:\n",
    "\n",
    "-   There is something wrong with the arguments the function is getting -- that is, a precondition is violated.\n",
    "\n",
    "-   There is something wrong with the function -- that is, a postcondition is violated.\n",
    "\n",
    "-   The caller is doing something wrong with the return value.\n",
    "\n",
    "To rule out the first possibility, you can add a `print` statement at the beginning of the function that displays the values of the parameters (and maybe their types).\n",
    "Or you can write code that checks the preconditions explicitly.\n",
    "\n",
    "If the parameters look good, you can add a `print` statement before each `return` statement and display the return value.\n",
    "If possible, call the function with arguments that make it easy check the result. \n",
    "\n",
    "If the function seems to be working, look at the function call to make sure the return value is being used correctly -- or used at all!\n",
    "\n",
    "Adding `print` statements at the beginning and end of a function can help make the flow of execution more visible.\n",
    "For example, here is a version of `factorial` with print statements:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "id": "1d50479e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def factorial(n):\n",
    "    space = ' ' * (4 * n)\n",
    "    print(space, 'factorial', n)\n",
    "    if n == 0:\n",
    "        print(space, 'returning 1')\n",
    "        return 1\n",
    "    else:\n",
    "        recurse = factorial(n-1)\n",
    "        result = n * recurse\n",
    "        print(space, 'returning', result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c044111",
   "metadata": {},
   "source": [
    "`space` is a string of space characters that controls the indentation of\n",
    "the output. Here is the result of `factorial(3)` :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 140,
   "id": "798db5c4",
   "metadata": {},
   "outputs": [],
   "source": [
    "factorial(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43b3e408",
   "metadata": {},
   "source": [
    "If you are confused about the flow of execution, this kind of output can be helpful.\n",
    "It takes some time to develop effective scaffolding, but a little bit of scaffolding can save a lot of debugging."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b7c3962f",
   "metadata": {},
   "source": [
    "## Glossary\n",
    "\n",
    "**return value:**\n",
    "The result of a function. If a function call is used as an expression, the return value is the value of the expression.\n",
    "\n",
    "**pure function:**\n",
    "A function that does not display anything or have any other effect, other than returning a return value.\n",
    "\n",
    "\n",
    "**dead code:**\n",
    "Part of a program that can never run, often because it appears after a `return` statement.\n",
    "\n",
    "**incremental development:**\n",
    "A program development plan intended to avoid debugging by adding and testing only a small amount of code at a time.\n",
    "\n",
    "**scaffolding:**\n",
    " Code that is used during program development but is not part of the final version.\n",
    "\n",
    "**Turing complete:**\n",
    "A language, or subset of a language, is Turing complete if it can perform any computation that can be described by an algorithm.\n",
    "\n",
    "**input validation:**\n",
    "Checking the parameters of a function to make sure they have the correct types and values"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ff7b1edf",
   "metadata": {},
   "source": [
    "## Exercises"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "id": "e0f15ca4",
   "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": "0da2daaf",
   "metadata": {},
   "source": [
    "### Ask a virtual assistant\n",
    "\n",
    "In this chapter, we saw an incorrect function that can end without returning a value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "90b4979f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def absolute_value_wrong(x):\n",
    "    if x < 0:\n",
    "        return -x\n",
    "    if x > 0:\n",
    "        return x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "69563d4b",
   "metadata": {},
   "source": [
    "And a version of the same function that has dead code at the end."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9217f038",
   "metadata": {},
   "outputs": [],
   "source": [
    "def absolute_value_extra_return(x):\n",
    "    if x < 0:\n",
    "        return -x\n",
    "    else:\n",
    "        return x\n",
    "    \n",
    "    return 'This is dead code.'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9fe8ae2e",
   "metadata": {},
   "source": [
    "And we saw the following example, which is correct but not idiomatic."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3168489b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_divisible(x, y):\n",
    "    if x % y == 0:\n",
    "        return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "14f52688",
   "metadata": {},
   "source": [
    "Ask a virtual assistant what's wrong with each of these functions and see if it can spot the errors or improve the style.\n",
    "\n",
    "Then ask \"Write a function that takes coordinates of two points and computes the distance between them.\" See if the result resembles the version of `distance` we wrote in this chapter."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fd23bb60",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "Use incremental development to write a function called `hypot` that returns the length of the hypotenuse of a right triangle given the lengths of the other two legs as arguments.\n",
    "\n",
    "Note: There's a function in the math module called `hypot` that does the same thing, but you should not use it for this exercise!\n",
    "\n",
    "Even if you can write the function correctly on the first try, start with a function that always returns `0` and practice making small changes, testing as you go.\n",
    "When you are done, the function should only return a value -- it should not display anything."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "62267fa3",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5f8fa829",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3d129b03",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "030179b6",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d737b468",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "77a74879",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0521d267",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "468a31e9",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "abbe3ebf",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "651295e4",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0a66d82a",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "Write a boolean function, `is_between(x, y, z)`, that returns `True` if $x < y < z$ or if \n",
    "$z < y < x$, and`False` otherwise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0a4ee482",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c12f318d",
   "metadata": {
    "tags": []
   },
   "source": [
    "You can use these examples to test your function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "956ed6d7",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "is_between(1, 2, 3)  # should be True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a994eaa6",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "is_between(3, 2, 1)  # should be True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4318028d",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "is_between(1, 3, 2)  # should be False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "05208c8b",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "is_between(2, 3, 1)  # should be False"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "57f06466",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "The Ackermann function, $A(m, n)$, is defined:\n",
    "\n",
    "$$\\begin{aligned}\n",
    "A(m, n) = \\begin{cases} \n",
    "              n+1 & \\mbox{if } m = 0 \\\\ \n",
    "        A(m-1, 1) & \\mbox{if } m > 0 \\mbox{ and } n = 0 \\\\ \n",
    "A(m-1, A(m, n-1)) & \\mbox{if } m > 0 \\mbox{ and } n > 0.\n",
    "\\end{cases} \n",
    "\\end{aligned}$$ \n",
    "\n",
    "Write a function named `ackermann` that evaluates the Ackermann function.\n",
    "What happens if you call `ackermann(5, 5)`?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7eb85c5c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "85f7f614",
   "metadata": {
    "tags": []
   },
   "source": [
    "You can use these examples to test your function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "687a3e5a",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "ackermann(3, 2)  # should be 29"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c49e9749",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "ackermann(3, 3)  # should be 61"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8497dec4",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "ackermann(3, 4)  # should be 125"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4994ceae",
   "metadata": {
    "tags": []
   },
   "source": [
    "If you call this function with values bigger than 4, you get a `RecursionError`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "76be4d15",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "%%expect RecursionError\n",
    "\n",
    "ackermann(5, 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b8af1586",
   "metadata": {
    "tags": []
   },
   "source": [
    "To see why, add a print statement to the beginning of the function to display the values of the parameters, and then run the examples again."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7c2ac0a4",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Exercise\n",
    "\n",
    "A number, $a$, is a power of $b$ if it is divisible by $b$ and $a/b$ is\n",
    "a power of $b$. Write a function called `is_power` that takes parameters\n",
    "`a` and `b` and returns `True` if `a` is a power of `b`. Note: you will\n",
    "have to think about the base case."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0bcba5fe",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e93a0715",
   "metadata": {
    "tags": []
   },
   "source": [
    "You can use these examples to test your function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4b6656e6",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "is_power(65536, 2)   # should be True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "36d9e92a",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "is_power(27, 3)  # should be True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1d944b42",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "is_power(24, 2)  # should be False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "63ec57c9",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "is_power(1, 17)   # should be True"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a33bbd07",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "The greatest common divisor (GCD) of $a$ and $b$ is the largest number\n",
    "that divides both of them with no remainder.\n",
    "\n",
    "One way to find the GCD of two numbers is based on the observation that\n",
    "if $r$ is the remainder when $a$ is divided by $b$, then $gcd(a,\n",
    "b) = gcd(b, r)$. As a base case, we can use $gcd(a, 0) = a$.\n",
    "\n",
    "Write a function called `gcd` that takes parameters `a` and `b` and\n",
    "returns their greatest common divisor."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4e067bfb",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "efbebde9",
   "metadata": {
    "tags": []
   },
   "source": [
    "You can use these examples to test your function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2a7c1c21",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "gcd(12, 8)    # should be 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5df00229",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "gcd(13, 17)   # should be 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8bec38b3",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "a7f4edf8",
   "metadata": {
    "tags": []
   },
   "source": [
    "[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/)"
   ]
  }
 ],
 "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
}