wk4/MY470_wk4_lecture.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### MY470 Computer Programming\n",
    "# ⚙️ Functions in Python\n",
    "### Week 4 Lecture"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Overview\n",
    "\n",
    "* Decomposition and abstraction\n",
    "* Defining and calling functions\n",
    "* Variable scope\n",
    "* Modules and packages\n",
    "* Recursion\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## From Last Week: [Control Flow](https://www.youtube.com/watch?v=k0xgjUhEG3U)\n",
    "\n",
    "![Three categories of control flow](figs/control_flow.png \"Three categories of control flow\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Functions\n",
    "\n",
    "\n",
    "* Built-in\n",
    "  * `len()`, `max()`, `range()`, `open()`, etc.\n",
    "* User-defined\n",
    "  * You\n",
    "  * Collaborators\n",
    "  * The open-source community\n",
    "  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Decomposition and Abstraction\n",
    "\n",
    "![Decomposition and abstraction](figs/decomposition_abstraction.png \"Decomposition and abstraction\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "* Decomposition allows to break the program into self-contained parts – it creates structure\n",
    "* Abstraction allows to use code as if it is a black box – it hides detail"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Defining and Calling Functions\n",
    "\n",
    "### Defining a function\n",
    "\n",
    "```\n",
    "def *function_name*(*list of parameters*):\n",
    "    *body of function*\n",
    "```\n",
    "\n",
    "### Calling a function\n",
    "\n",
    "```\n",
    "*function_name*(*arguments*)\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## When the Function is Used, the Parameters are Bound to the Arguments\n",
    "\n",
    "```\n",
    "def *function_name*(*list of parameters*):\n",
    "    *body of function*\n",
    "\n",
    "*function_name*(*arguments*)\n",
    "```\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n"
     ]
    }
   ],
   "source": [
    "def get_larger(x, y):\n",
    "    \"\"\"Assumes x and y are of numeric type.\n",
    "    Returns the larger of x and y.\n",
    "    \"\"\"\n",
    "    if x > y:\n",
    "        # The execution of a `return` statement terminates the function call\n",
    "        return x\n",
    "    else:\n",
    "        return y\n",
    "    \n",
    "m = get_larger(3, 4)\n",
    "print(m)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Note that `def` and `return` are reserved words in Python. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## A Function Call Always Returns a Value\n",
    "\n",
    "* The execution of a `return` statement terminates the function call\n",
    "* The function call also terminates when there are no more statements to execute\n",
    "* If no expression follows `return` or there is no `return` statement, the function returns `None`       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 6 None\n"
     ]
    }
   ],
   "source": [
    "def get_larger(x, y):\n",
    "    if x > y:\n",
    "        return x\n",
    "    if y > x:\n",
    "        return y\n",
    "\n",
    "ex1 = get_larger(3, 5)\n",
    "ex2 = get_larger(6, 4)\n",
    "ex3 = get_larger(3, 3)\n",
    "\n",
    "print(ex1, ex2, ex3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Functions with Multiple Returned Values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(10, 6)\n",
      "10\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "def double_one(a):\n",
    "    return 2*a\n",
    "\n",
    "def double_two(a, b):\n",
    "    return 2*a, 2*b\n",
    "\n",
    "x = double_two(5, 3)\n",
    "print(x)\n",
    "\n",
    "# You can unpack the tuple in two separate variables\n",
    "x1, x2 = double_two(5, 3)\n",
    "print(x1)\n",
    "print(x2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Functions: Exercise"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "# Write a function that reverses a string, e.g. \"now\" -> \"won\".\n",
    "# Then call the function to reverse each of the strings in the list.\n",
    "\n",
    "to_reverse = ['doc', 'keep', 'lap', 'lever', 'nap', 'nip', 'war']\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Positional vs. Keyword Arguments"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 2 1\n",
      "3 2 1\n",
      "3 2 1\n"
     ]
    }
   ],
   "source": [
    "def print_reverse(first, second, third):\n",
    "    print(third, second, first)\n",
    "    \n",
    "print_reverse(1, 2, 3)\n",
    "print_reverse(third=3, second=2, first=1)\n",
    "print_reverse(1, second=2, third=3)\n",
    "# print_reverse(first=1, 2, 3)  # Gives a syntax error"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### Keyword arguments cannot come before positional arguments!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Default Parameter Values\n",
    "\n",
    "* Default values allow to call a function with fewer arguments than specified\n",
    "* Default arguments cannot come before non-default arguments!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The quick brown fox jumps over the lazy dog.\n",
      "The quick brown fox jumps over the lazy dog.\n",
      "The quick brown fox jumps over the lazy dog\n"
     ]
    }
   ],
   "source": [
    "def pretty_print(lst, sep, fullstop=True, capitalize=True):\n",
    "    toprint = sep.join(lst)\n",
    "    if fullstop:\n",
    "        toprint += '.'\n",
    "    if capitalize:\n",
    "        toprint = toprint.capitalize()\n",
    "    print(toprint)\n",
    "\n",
    "wordlst = ['the', 'quick', 'brown', 'fox', 'jumps', \n",
    "           'over', 'the', 'lazy', 'dog']  # an English pangram\n",
    "\n",
    "pretty_print(wordlst, ' ', True, True)\n",
    "pretty_print(wordlst, ' ')\n",
    "pretty_print(wordlst, ' ', False)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Functions with Variable Number of Arguments"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2]\n",
      "[2, 4, 6]\n",
      "[]\n"
     ]
    }
   ],
   "source": [
    "def double_many(*args):\n",
    "    return [2*i for i in args]\n",
    "\n",
    "print(double_many(1))\n",
    "print(double_many(1, 2, 3))\n",
    "print(double_many())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## A Function Defines a New Scope\n",
    "\n",
    "* Scope = name space"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "def func(x, y):\n",
    "    x += 1\n",
    "    # x is a parameter, z is a local variable\n",
    "    z = x + y   # z, x, and y exist only in the scope of the definition of func\n",
    "    return z\n",
    "\n",
    "x = 1\n",
    "res = func(x, 5)\n",
    "\n",
    "print(x)  # x has not changed \n",
    "#print(z)  # Returns an error\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### This means you can reuse your favorite variable names in different functions!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## The Global Scope"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "GLOBVAR = 3\n",
    "\n",
    "def print_global():\n",
    "    # Since GLOBVAR is not defined in the function, it is treated as global\n",
    "    print(GLOBVAR)  \n",
    "\n",
    "print_global()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### Use CAPITALS to name global variables!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Function Arguments: Exercise\n",
    "\n",
    "Find the errors in the code below:\n",
    "\n",
    "```\n",
    "def find_char(astring, achar, start=0, end):\n",
    "    \"\"\"Find and return the index of achar in astring.\n",
    "    Return None if achar does not occur in astring.\n",
    "    \"\"\"\n",
    "    i = start\n",
    "    if end == None:\n",
    "        end = len(astring)\n",
    "\n",
    "    found = False\n",
    "    while i < end and not found:\n",
    "        if astring[i] == achar:\n",
    "            found = True\n",
    "        else:\n",
    "            i += 1\n",
    "            \n",
    "    if found:\n",
    "        return i\n",
    "    \n",
    "    return None\n",
    "\n",
    "\n",
    "mystring = \"What goes around comes around.\"\n",
    "\n",
    "print(find_char(mystring, 'e', start=2, 24))\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Modules\n",
    "\n",
    "* For large programs, store different parts in `.py` files\n",
    "* Get access using `import` statements"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "She said: \"Hello!\"\n"
     ]
    }
   ],
   "source": [
    "import module\n",
    "\n",
    "module.my_func('Hello!')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "She said: \"Hello there!\"\n"
     ]
    }
   ],
   "source": [
    "import module as md\n",
    "\n",
    "md.my_func('Hello there!')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "She said: \"HELLO! DO YOU HEAR ME?\"\n"
     ]
    }
   ],
   "source": [
    "# You should be careful with this one: there will be a conflict if you\n",
    "# import a different module that also has a function called my_func()\n",
    "from module import *\n",
    "\n",
    "my_func('HELLO! DO YOU HEAR ME?')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Modules, Packages, and Libraries\n",
    "\n",
    "### Module \n",
    "The module is a simple Python file that contains collections of functions and global variables. \n",
    "\n",
    "### Package\n",
    "A collection of modules within a directory. \n",
    "\n",
    "### Library\n",
    "A library is an umbrella term that loosely means \"a bundle of code.\" These can have tens or even hundreds of individual modules that can provide a wide range of functionality."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Useful Python Modules\n",
    "\n",
    "https://docs.python.org/3/library/\n",
    "\n",
    "* `re` – Regular expression operations\n",
    "* `datetime` – Basic date and time types\n",
    "* `math` – Mathematical functions\n",
    "* `random` – Generate pseudo-random numbers\n",
    "* `os.path` – Common pathname manipulations\n",
    "* `pickle` — Python object serialization\n",
    "* `csv` — CSV file reading and writing\n",
    "* `json` — JSON encoder and decoder\n",
    "* ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Useful Python Packages\n",
    "\n",
    "* `numpy` – Scientific computing with multi-dimensional arrays\n",
    "* `pandas` – Data anlysis with table-like structures (R, pretty much)\n",
    "* `statsmodels` – Statistical data analysis with linear models\n",
    "* `scikit-learn` – Data mining and machine learning\n",
    "* `networkx` – Network analysis\n",
    "* `matplotlib` – Plotting\n",
    "* ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Using Modules and Packages in Python \n",
    "\n",
    "### How does a programmer write an essay?\n",
    "\n",
    "![Modules and packages in Python](figs/python_modules.png \"Modules and packages in Python\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Functions Calling Other Functions\n",
    "\n",
    "![Functions calling functions](figs/functions.png \"Functions calling functions\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Functions Calling Themselves, A.K.A. Recursion\n",
    "\n",
    "**Recursion** is a problem-solving method where the solution to a problem depends on solutions to smaller instances of the same problem.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15\n"
     ]
    }
   ],
   "source": [
    "# Consider the sum of elements in a list\n",
    "\n",
    "lst = [1, 2, 3, 4, 5]\n",
    "# We want (1 + 2 + 3 + 4 + 5), which is equivalent to (1 + (2 + (3 + (4 + 5)))).\n",
    "# This suggests that we can reduce the problem to the problem of adding two numbers.\n",
    "\n",
    "def list_sum(lst):\n",
    "    \"\"\"Assumes lst is a sequence of numeric types.\n",
    "    Returns the sum of all elements in lst.\n",
    "    \"\"\"\n",
    "    if len(lst) == 1:\n",
    "        return lst[0]   # base case\n",
    "    else:\n",
    "        return lst[0] + list_sum(lst[1:])   # recursive case\n",
    "    \n",
    "print(list_sum(lst))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## How Recursion Works"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def list_sum(lst):\n",
    "    if len(lst) == 1:  \n",
    "        return lst[0]\n",
    "    else:\n",
    "        return lst[0] + list_sum(lst[1:]) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "![Recursion](figs/recursion.png \"Recursion\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Writing Recursive Procedures\n",
    "\n",
    "1. Define the general case\n",
    "2. Define the base case\n",
    "3. Ensure the base case is reached after a finite number of recursive calls"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Recursion Example: The Factorial Function `n!`*\n",
    "\n",
    "\\* The product of all positive integers less than or equal to n\n",
    "\n",
    "![Factorial for estimating permutations](figs/factorial_permutation.jpg \"Factorial for estimating permutations\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Recursion Example: What Is `n!`?\n",
    "\n",
    "1. General case: `n! = n * (n-1)!`\n",
    "2. Base case: `1! = 1`\n",
    "3. Base case reached when `n==1`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "before 5\n",
      "before 4\n",
      "before 3\n",
      "before 2\n",
      "base case 1\n",
      "after 2 2\n",
      "after 3 6\n",
      "after 4 24\n",
      "after 5 120\n",
      "120\n"
     ]
    }
   ],
   "source": [
    "def factorial(n):\n",
    "    \"\"\"Assumes n is a positive integer.\n",
    "    Estimates n!.\n",
    "    \"\"\"\n",
    "    if n == 1:\n",
    "        print('base case', n)\n",
    "        answer = 1\n",
    "    else:\n",
    "        print('before', n)\n",
    "        answer = n * factorial(n-1)\n",
    "        print('after', n, answer)\n",
    "    return answer\n",
    "\n",
    "print(factorial(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## From Last Week: Approximation with Bisection Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5.00030517578125\n"
     ]
    }
   ],
   "source": [
    "def bisec_search(x, epsilon):\n",
    "    \"\"\"Assumes x and epsilon are numeric.\n",
    "    Finds an approximation to the square root \n",
    "    of a number x using bisection search.\n",
    "    \"\"\"\n",
    "\n",
    "    # Define interval for search\n",
    "    low = 0\n",
    "    high = max(1, x)\n",
    "\n",
    "    # Start in the middle\n",
    "    guess = (low + high) / 2 \n",
    "\n",
    "    # Narrow down search interval until guess close enough\n",
    "    while abs(guess**2 - x) >= epsilon:\n",
    "        if guess**2 < x:\n",
    "            low = guess\n",
    "        else:\n",
    "            high = guess\n",
    "        guess = (low + high) / 2\n",
    "        \n",
    "    return guess\n",
    "\n",
    "print(bisec_search(25, 0.01))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Recursion Example: Approximation with Bisection Search\n",
    "\n",
    "1. General case: \n",
    "```\n",
    "guess = (low + high) / 2\n",
    "if guess**2 < x: low = guess\n",
    "else: high = guess\n",
    "```          \n",
    "2. Base case: `return guess`\n",
    "3. The base case is reached when `abs(guess**2 - x) < epsilon`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5.00030517578125\n"
     ]
    }
   ],
   "source": [
    "def bisec_search_rec(low, high, x, epsilon):\n",
    "    \n",
    "    # Start in the middle of the interval\n",
    "    guess = (low + high) / 2\n",
    "    \n",
    "    if abs(guess**2 - x) < epsilon:\n",
    "        return guess\n",
    "    else:\n",
    "        if guess**2 < x:\n",
    "            return bisec_search_rec(guess, high, x, epsilon)\n",
    "        else:\n",
    "            return bisec_search_rec(low, guess, x, epsilon)\n",
    "\n",
    "print(bisec_search_rec(0, 25, 25, 0.01))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Recursion: Exercise\n",
    "\n",
    "Write a function `power(x, p)` that uses recursion to calculate the value of `x` to the power of `p`, or $x^p$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Recursion Example: The Fibonacci Numbers*\n",
    "\n",
    "\\* An integer sequence where every number after the first two is the sum of the two preceding ones: `0, 1, 1, 2, 3, 5, 8, 13, ...` (modern version)\n",
    "\n",
    "![Fibonacci numbers for rabbit multiplication](figs/fibonacci_rabbits.jpg \"Fibonacci numbers for rabbit multiplication\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Recursion Example: What Is the n-th Fibonacci Number?\n",
    "\n",
    "1. General case: `fib(n) = fib(n - 1) + fib(n - 2)` \n",
    "\n",
    "2. Base case: `fib(0) = 0`, `fib(1) = 1`\n",
    "\n",
    "3. The base case is reached when `n == 0` or `n == 1`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "1\n",
      "2\n",
      "3\n",
      "5\n",
      "8\n",
      "13\n",
      "21\n",
      "34\n"
     ]
    }
   ],
   "source": [
    "def fib(n):\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    elif n == 1:\n",
    "        return 1\n",
    "    else:\n",
    "        return fib(n - 1) + fib(n - 2)\n",
    "\n",
    "for i in range(10): \n",
    "    print(fib(i))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Recursion Could be Quite Inefficient\n",
    "\n",
    "Even if you can formulate a problem in recursive terms, it does not mean that recursion is the most efficient way to solve it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def fib_rec(n):\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    elif n == 1:\n",
    "        return 1\n",
    "    else:\n",
    "        return fib_rec(n - 1) + fib_rec(n - 2)\n",
    "\n",
    "\n",
    "def fib_ite(n):    \n",
    "    first = 0\n",
    "    second = 1\n",
    "    for i in range(n):\n",
    "        old_first = first # remember what first was\n",
    "        first = second # shift the first forward\n",
    "        second = old_first + first # estimate the new second\n",
    "    return first"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Comparing the Execution Time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Recursion: 1.228182077407837 seconds\n",
      "Iteration: 4.8160552978515625e-05 seconds\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "from time import time\n",
    "\n",
    "start_time = time()\n",
    "fib33_rec = fib_rec(33)\n",
    "print('Recursion:', (time() - start_time), 'seconds')\n",
    "\n",
    "start_time = time()\n",
    "fib33_ite = fib_ite(33)\n",
    "print('Iteration:', (time() - start_time), 'seconds')\n",
    "\n",
    "print(fib33_rec == fib33_ite) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "An alternative way to do this is with the `timeit` module. By default, it runs the code snippet 1,000,000 times and then returns the execution time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Recursion: 2.6662395560015284\n",
      "Iteration: 0.44653458399989177\n"
     ]
    }
   ],
   "source": [
    "from timeit import timeit\n",
    "\n",
    "print('Recursion:', timeit(\"fib_rec(6)\", setup=\"from __main__ import fib_rec\"))\n",
    "print('Iteration:', timeit(\"fib_ite(6)\", setup=\"from __main__ import fib_ite\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## The Fibonacci Numbers: The Number of Recursive Calls Increases Exponentially with `n`\n",
    "\n",
    "![Fibonacci](figs/fibonacci.png \"Fibonacci\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "The calls form a binary tree because there are two recursive self-calls."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Any Recursive Algorithm Can Be Transformed into an Iterative One! \n",
    "\n",
    "![Recursion and iteration](figs/recursion_iteration.jpg \"Recursion and iteration\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Recursion and Efficiency: Exercise\n",
    "\n",
    "Place the functions `bisec_search()` and `bisec_search_rec()` we presented above in a module called `bisec`. Then use the `timeit()` function from the `timeit` module in the cell below to compare the performance of these two functions, calling them from the module."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Functions\n",
    "\n",
    "Functions provide **abstraction** and **decomposition**:\n",
    "\n",
    "* Break large problems into smaller ones\n",
    "* Hide the gory implementation details\n",
    "* Present elementary building blocks that can be recombined to solve new problems\n",
    "* Improve code legibility\n",
    "* Enable collaboration\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "-------\n",
    "\n",
    "* **Lab**: Writing and calling functions in Python; function specification\n",
    "* **Assessment**: PS2 released today, due 12:00 noon next Monday\n",
    "* **Next week**: Classes in Python"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "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.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}