Lab 1.4.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Edited: 12th September 2023*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CMM201 &mdash; Lab 1.4\n",
    "\n",
    "In this lab we will learn about conditional execution, also known as \"branching\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Boolean Logic Values"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the videos we saw Boolean logic values, which shortens to the keyword `bool`.\n",
    "\n",
    "The following is a bool."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And using comparison operators we can create a bool, also."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "1 < 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also combine Boolean expressions using `not`, `and`, `or`.\n",
    "\n",
    "**Note to Programmers:** If you have used other programming languages you may be used to using symbols for these such as `&`, and `|`, but don't use these in Python as they mean bitwise operations. Only use the English words `and`, `or`, and `not`.\n",
    "\n",
    "**(a)** Before running each cell below, try to predict what the resulting bool will be (`True` or `False`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "1 + 1 == 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "True and 1 + 1 == 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "False and 1 + 1 == 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "False or 1 + 1 == 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "1 < 2 and not 3 > 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = 1\n",
    "\n",
    "x == 7 or x < 2 and not 1 + x == 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Equivalent Expressions\n",
    "\n",
    "There are different ways to write a single Boolean expression.\n",
    "\n",
    "In this module, we won't go in to the full detail of the laws of Boolean algebra, but we will look at a few simple concepts.\n",
    "\n",
    "Normally when using real Python examples we will use lowercase letters like `user_is_logged_on`, but since a lot of maths texts use single uppercase English letter for examples relating to Boolean algebra, we will borrow that convention here to make things easier to read. So you'll see examples below using `A` and `B` for example Booleans, and using values like `x` and `y` for example numbers. When we get to more useful examples we'll use clearer variable names."
   ]
  },
  {
   "cell_type": "markdown",
   "source": [
    "### The Law of Double Negation"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For any Boolean expression `A`, the expression `not not A` is equivalent to `A`.\n",
    "\n",
    "If `A` is True, then `not A` is false, adding another `not` gets us back to True."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = True\n",
    "\n",
    "not not A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = False\n",
    "\n",
    "not not A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So any even number of `not`s in a row can be deleted.\n",
    "\n",
    "Any odd number of `not`s in a row can be replaced by just one."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(b)** Simplify the Boolean expression (don't eliminate the variables). You should still get `True`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = 1\n",
    "y = 2\n",
    "\n",
    "not not not not x == 1 and not not not not not y > 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also apply double negation when we have comparison operators."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`==` is the opposite of `!=`\n",
    "\n",
    "`<` is the opposite of `>=`\n",
    "\n",
    "`>` is the opposite of `<=`\n",
    "\n",
    "So for example, `not x == y` and be replaced with `x != y` (or visa-versa)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(c)** Simplify the expressions so there are no instances of `not`. (don't eliminate variables)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = 5\n",
    "y = 42\n",
    "\n",
    "not x <= 5 or not y > 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = 10\n",
    "y = 9\n",
    "\n",
    "x == 7 and not x != y or not not not x == 7 and not y < 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### De Morgan’s Theorem\n",
    "\n",
    "A very famous theorem in Boolean algebra which establishes a relationship between `and` and `or` using `not`.\n",
    "\n",
    "Let's look at an example to explain it better."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = True\n",
    "B = True\n",
    "\n",
    "A or B"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can invert the inputs using two `not`s, and replace the `or` with an `and`, then we get an expression which is exactly the **opposite** of our original expression."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "not A and not B"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But we don't want the opposite, we want the same, so to get us back to the original, we negate the result. Since the precedence of `not` normally applies before the other logical operators, we need to use brackets!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "not (not A and not B)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What if we started with an expression which already had `not`s?\n",
    "\n",
    "In the following expression:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = True\n",
    "x = 5\n",
    "\n",
    "not A or x < 10"
   ]
  },
  {
   "cell_type": "markdown",
   "source": [
    "Obserse that the two clauses are:\n",
    "\n",
    "    not A\n",
    "    \n",
    "and\n",
    "\n",
    "    x < 10"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "we can apply the following steps;\n",
    "\n",
    "1. invert the operands\n",
    "2. replace `or` with `and` (or visa-versa)\n",
    "3. invert the output\n",
    "\n",
    "The result of applying these steps to\n",
    "\n",
    "    not A or x < 10\n",
    "    \n",
    "is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "not (not not A and not x < 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But wait, we have two `not`s in a row here. Let's delete them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "not (A and not x < 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Plus we can remove the second `not` there by flipping the comparison."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "not (A and x >= 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Warning:**  a common error is thinking the opposite of `<` is `>`, it is not. This is an easy mistake to make.\n",
    "\n",
    "So we see that `not A or x < 10` is equivalent to `not (A and x >= 10)`.\n",
    "\n",
    "**(d)** Apply de Morgan's Theorem to the expressions below. If you have a `not` next to a comparison, remove it and negate comparison, e.g. turn `not x == y` to `x != y`.\n",
    "\n",
    "Note: The expression may or may not become simpler. In practice you would probably only want to apply this theorem in cases where it makes your code simpler."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = True\n",
    "B = False\n",
    "\n",
    "not B and A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = 7\n",
    "y = 9\n",
    "\n",
    "not x == 7 or y > 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "source": [
    "The main point to remember is that there are different ways to write the same Boolean logical expression."
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Simplifying Ranges\n",
    "\n",
    "When we are dealing with numbers, we can make some further simplifications by thinking about whether one comparison make another always `True` or always `False`.\n",
    "\n",
    "For example:\n",
    "\n",
    "`x > 10 and x > 5` can be replaced with `x > 10`, because any number satisfying `x > 10` will also satisfy `x > 5`.\n",
    "\n",
    "`x > 10 or x > 5` can be replaced with `x > 5` for the same reason.\n",
    "\n",
    "`x < 10 or x > 5` can be replaced with `True` because all numbers are either less than 10 or greater than 5 (or both).\n",
    "\n",
    "`x => 10 and x <= 5` can be replaced with `False` for the same reason.\n",
    "\n",
    "It helps to grab a pen and sheet of paper and draw out a number line and check where the conditions overlap.\n",
    "\n",
    "**(e)** simplify the ranges below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x < 10 or x < 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x < 10 and x > 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python also has a special chained syntax for writing the condition where a value is in between two others.\n",
    "\n",
    "For example:\n",
    "    \n",
    "`10 < x <= 100` means `10 < x and x <= 100`\n",
    "\n",
    "This syntax is often clearer and easier to understand than the code with `and`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(f)** Simplify the following to a chained comparison syntax."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "1 < x and x < 100 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x > 6 and x <= 16"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x <= 0 or x > 15"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## If Statements and Code Blocks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Without code blocks, our code just runs exactly once, top-to-bottom."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print('line 1')\n",
    "print('line 2')\n",
    "print('line 3')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With conditional code blocks, we can have only certain lines run. For example, if `x` is greater than 100, the first print statement will run, otherwise the second will run. Later in the module, we will see another type of code block (iteration).\n",
    "\n",
    "Just like with functions, by Python convention you should use 4 spaces to indent. Do not use 2 spaces, do not use tabs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = 100000\n",
    "\n",
    "if x > 100:\n",
    "    print('x is a large number')\n",
    "else:\n",
    "    print('x is a small number')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The condition can be as complicated as you need it to be, and the body of the conditional block can contain multiple statements."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = 10\n",
    "y = 9\n",
    "\n",
    "if x == 7 and not x != y or not not not x == 7 and not y < 6:\n",
    "    print('our annoyingly confusing expression was True')\n",
    "    print('x is ', x)\n",
    "    print('y is ', y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Note to programmers:** In C-like languages you will use curly brackets `{` and `}` to indicate the body of an if block, Python uses syntactically significant whitespace. The 4 spaces tells Python which lines are inside the if block.\n",
    "\n",
    "We can also nest if statements.\n",
    "\n",
    "**(g)** Modify the value of `x` below a few times and rerun to explore different branches. Before running, try to predict which branches will be run, and check if your are correct.\n",
    "\n",
    "Try to have it print:\n",
    "\n",
    "    x is larger than 1\n",
    "    but not larger than 10\n",
    "\n",
    "**only** by changing the value of `x`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = 50\n",
    "\n",
    "if x > 1:\n",
    "    print('x is larger than 1')\n",
    "    if x > 10:\n",
    "        print('and larger than 10')\n",
    "    else:\n",
    "        print('but not larger than 10')\n",
    "else:\n",
    "    print('x is not larger than 1')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(h)** How many possible outcomes are there (how many different results in the standard output could you see?)"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Functions and Booleans\n",
    "\n",
    "A very common use of Booleans and conditional execution is piecewise functions, and functions which return Booleans.\n",
    "\n",
    "A piecewise function is one like the absolute value function we saw before, which some formula is applied for some ranges (e.g. `absval(x)` returns `x` for non-negative `x`, and returns `-x` for negative `x`)\n",
    "\n",
    "We could have written it like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def absval(x):\n",
    "    if x < 0:\n",
    "        return -x\n",
    "    else:\n",
    "        return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Usually, we can't just delete an `else:` and hope the program still works, however, if the condition is true, the line `return -x` will break us out of the function, so we can refactor this as:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def absval(x):\n",
    "    if x < 0:\n",
    "        return -x\n",
    "    return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There is also a ternary operator in Python which lets us squeeze two possible results into one line:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def absval(x):\n",
    "    return -x if x < 0 else x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But, sometimes this can be harder to read and understand. So it's not often recommended. We will usually not use the ternary operator in CMM201.\n",
    "\n",
    "Perhaps this version of the program is easier to read:\n",
    "\n",
    "    def absval(x):\n",
    "        if x < 0:\n",
    "            return -x\n",
    "        return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By the way, there is a built-in version of this function called `abs`. In practice, don't write your own version of this function, just use the built-in version. We only wrote our own as a programming exercise to demonstrate how to write a piecewise function!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "abs(-5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another common way we use Booleans and functions is to return a bool. This is very common in data filtering, which we will come to in Unit 2.1.\n",
    "\n",
    "Let's say we wanted to create a function `is_senior` which takes a person's `age` as an argument, and turns `True` if the person is at least 65.\n",
    "\n",
    "An obvious way to write this is as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_senior(age):\n",
    "    if age >= 65:\n",
    "        return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But we can refactor this because the expression `age >= 65` is a bool, we can just return the bool."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_senior(age):\n",
    "    return age >= 65"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Often, functions can be written in relatively compact ways like this, and you should look for ways to refactor your code like this."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(i)** Refactor the following code so that the body of the function is a single line.\n",
    "\n",
    "**Hint:** Use Boolean operators!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# checks drinking age for UK and US users\n",
    "def is_drinking_age(age, usa):\n",
    "    if usa:\n",
    "        if age >= 21:\n",
    "            return True    # drinking age 21 for USA\n",
    "        else:\n",
    "            return False\n",
    "    else:\n",
    "        if age >= 18:\n",
    "            return True    # drinking age 18 for UK\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the resulting one-line function might be easier to read and understand, or harder.\n",
    "\n",
    "Sometimes whether a specific refactoring is a good idea can be a little subjective. Refactoring for readability is subjective because it's about how well a human can understand your code, and different programmers may have different opinions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Revisiting Fibonacci"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the lecture (or lesson videos if you're following online from the videos), we saw the example of the Fibonacci sequence implemented as a recursive function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib(n):\n",
    "    if n == 1:\n",
    "        return 1\n",
    "    if n == 2:\n",
    "        return 1\n",
    "    return fib(n-2) + fib(n-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's test it out using `fib(7)`.\n",
    "\n",
    "The Fibonacci sequence goes as:\n",
    "\n",
    "1, 1, 2, 3, 5, 8, 13, 21, ...\n",
    "\n",
    "So the 7th number in the sequence is 13."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fib(7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We also saw that if you tried to calculate a very big number in this way, you would get stuck"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fib(50)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you start this calculation and realise it's not going to finish any time soon (You'll see the `[*]` next to the cell showing that it is still running).\n",
    "\n",
    "If you were learning to program in the early 1990's then your computer would be stuck and to fix this you may have to hit the power button on your computer. But don't do that! Today we can just click the \"stop\" icon in the toolbar to stop the program running.\n",
    "\n",
    "**Note:** This will result in an error message called `KeyboardInterrupt`. This is because the Jupyter environment implements the stop button by sending an interrupt signal to Python which is normally (in Python script mode or interactive Python) done with the keyboard.\n",
    "\n",
    "If there is too much output cluttering up your notebook while you work, you can right-click on the output cell and select `Clear Outputs` to remove the output for only that cell for now.\n",
    "\n",
    "If we run the function with a very large number as an argument, say 1000000000, we may either see the same behaviour of not responding, or we may actually see a different error `RecursionError`, which is where Python has made too many recursive calls and gives up, so we didn't need to stop it, it stopped itself."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fib(1000000000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recursion is a very natural way to calculate Fibonacci numbers because it uses the mathematical definition directly. But in a later unit, we will see a different way of calculating Fibonacci numbers which does not use recursion, and will allow us to calculate larger numbers!\n",
    "\n",
    "There are some cases where we will see behaviour like this from a recursive function, even when we don't give it a very large argument.\n",
    "\n",
    "What do you think will happen if you run this?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fib(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What happens? Can you work out why?\n",
    "\n",
    "We're going to make our function impure by adding some temporary logging code using the `print` function. This is for the purpose of debugging."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib(n):\n",
    "    print('calling fib for n =', n)\n",
    "    if n == 1:\n",
    "        return 1\n",
    "    if n == 2:\n",
    "        return 1\n",
    "    return fib(n-2) + fib(n-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's try it out for `fib(7)`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fib(7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can see we're logging all recursive calls. Eventually, it all calls reach `1` or `2`.\n",
    "\n",
    "`n==1` and `n==2` are called the '*base cases*', that is the cases where we don't make another recursive call. To correctly calculate the answer, a recursive function must eventually reach a base case and stop.\n",
    "\n",
    "What happens if we call `fib(0)`?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fib(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On my computer it runs until `n = -5906`. It's not going to stop normally because it has overshot the base cases. `n` will keep deceasing and will never reach 1 or 2, because we already started lower than that!\n",
    "\n",
    "What about `fib(6.5)`? We're not starting out lower than 1, we're starting above 1 and going down. So what do you think will happen? Run it and see if your prediction is correct."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fib(6.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(j)** What happens and why?"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the next unit we will discuss exceptions, and raising exceptions when expected conditions are not met (for example, if the input `n` is not valid.\n",
    "\n",
    "Exception allow us to halt straight away when conditions are not right, and can be caught allowing us to display a friendly error message to the user.\n",
    "\n",
    "**(k)** What values of `n` are invalid for `fib(n)`? i.e. For what values can we not find an answer?"
   ]
  },
  {
   "cell_type": "raw",
   "source": [],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## A Quick Fix\n",
    "\n",
    "By the way you're you're using Python 3.9 or later (such as the version we recommend as of September 2023, Python 3.11) you can make your `fib` function magically able to find larger values using `@cache`. As long as we don't go above the recursion limit."
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "from functools import cache\n",
    "\n",
    "@cache\n",
    "def fib(n):\n",
    "    if n == 1:\n",
    "        return 1\n",
    "    if n == 2:\n",
    "        return 1\n",
    "    return fib(n-2) + fib(n-1)\n",
    "\n",
    "print('fib(1000) = ')\n",
    "print(fib(1000))"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "This works by having the function remember function calls it's seen before and not recompute the same thing over and over. **Only use this on pure functions.**"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "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.9.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}