lectures/03_recursive-algorithms.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"dsci512_header.png\" width=\"600\">\n",
    "\n",
    "# Lecture 3\n",
    "\n",
    "Outline:\n",
    "\n",
    "- Recursion intro: random tree graphics (5 min)\n",
    "- Recursion intro: the details (35 min)\n",
    "- Break (5 min)\n",
    "- Binary search, revisited (5 min)\n",
    "- Multiple recursive calls (20 min)\n",
    "- Activities (time permitting)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Learning objectives\n",
    "\n",
    "* Explain what recursion is, and why both the base case(s) and recursive step(s) are essential.\n",
    "* Recognize problems for which a recursive solution is appropriate.\n",
    "* Write a recursive solution for a simple problem.\n",
    "* Compare and contrast recursion and iteration."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "%config InlineBackend.figure_formats = ['svg']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Recursion intro: random tree graphics (5 min)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Below: credit for the idea goes to [Paul Goldenberg](https://www.edc.org/staff/e-paul-goldenberg); thanks to [Dan Garcia](https://people.eecs.berkeley.edu/~ddgarcia/) for introducing this to us."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "jupyter": {
     "source_hidden": true
    }
   },
   "outputs": [],
   "source": [
    "def move_pen(x, y, angle, length):\n",
    "    \"\"\"\n",
    "    Moves a point from initial location of x and y according to\n",
    "    angle and length specified.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    x : float\n",
    "        initial location of pen on the x axis\n",
    "    y : float\n",
    "        initial location of pen on the y axis\n",
    "    angle : float\n",
    "        direction from initial location (0 means up)\n",
    "    length: distance from the initial location desired to move\n",
    "\n",
    "    Returns\n",
    "    -------\n",
    "    new_x : float\n",
    "        new location on the x axis \n",
    "    new_y : float\n",
    "        new location on the y axis \n",
    "\n",
    "    Examples\n",
    "    --------\n",
    "    >>> move_pen(0, 0, 90,2)\n",
    "    (2.0, 0)\n",
    "    >>> move_pen(0, 0, 180,2)\n",
    "    (0, -2.0)\n",
    "\n",
    "    \"\"\"\n",
    "    new_x = x + length * np.sin(angle * np.pi / 180.0)\n",
    "    new_y = y + length * np.cos(angle * np.pi / 180.0)\n",
    "    return new_x, new_y\n",
    "\n",
    "def branch(x, y, angle=0, length=1, marker=\".\"):\n",
    "    \"\"\"\n",
    "    Plot a shape at the end of a tree branch.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    x : float\n",
    "        initial location on the x axis\n",
    "    y : float\n",
    "        initial location on the y axis\n",
    "    angle : float, optional (default = 0)\n",
    "        not used, needed to conform to the same interface as vee\n",
    "    length: float, optional (default = 1)\n",
    "        not used, needed to conform to the same interface as vee\n",
    "    marker : str, optional (default = \".\")\n",
    "        the shape at the end of the branch\n",
    "    \"\"\"\n",
    "    plt.plot(x, y, marker=marker, markersize=\"15\",\n",
    "             markerfacecolor=\"None\", markeredgecolor=\"k\")\n",
    "\n",
    "def square(*args):\n",
    "    return branch(*args, marker=\"s\")\n",
    "\n",
    "def hexagon(*args):\n",
    "    return branch(*args, marker=\"h\")\n",
    "\n",
    "def star(*args, length=1):\n",
    "    return branch(*args, marker=\"*\")\n",
    "\n",
    "def vee(x=0, y=0, angle=0, length=1):\n",
    "    \"\"\"\n",
    "    Plots a tree with random shaped nodes given\n",
    "    a trunk location, branch angle and branch length.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    x : float, optional (default = 0)\n",
    "        location of pen on the x axis\n",
    "    y : float, optional (default = 5)\n",
    "        location of pen on the y axis\n",
    "    angle : float, optional (default = 0)\n",
    "        direction from location desired to move in degrees \n",
    "    length: float,  (default = 1)\n",
    "        distance from the location desired to move\n",
    "    \"\"\"\n",
    "#     plt.figure(figsize=(4,3))\n",
    "    \n",
    "    # possible shapes\n",
    "    shapes = [square, hexagon, star, vee, vee]\n",
    "\n",
    "    # branch left\n",
    "    shape = np.random.choice(shapes)\n",
    "    new_angle = angle - 20/np.pi\n",
    "    new_x, new_y = move_pen(x, y, new_angle, length)\n",
    "    plt.plot([x, new_x], [y, new_y], 'k')\n",
    "    shape(new_x, new_y, new_angle, length)\n",
    "\n",
    "    # branch right\n",
    "    shape = np.random.choice(shapes)\n",
    "    new_angle = angle + 20/np.pi\n",
    "    new_x, new_y = move_pen(x, y, new_angle, length)\n",
    "    plt.plot([x, new_x], [y, new_y], 'k')\n",
    "    shape(new_x, new_y, new_angle, length)\n",
    "\n",
    "    plt.xticks(())\n",
    "    plt.yticks(())\n",
    "    plt.xlim((-2, 2))\n",
    "    plt.ylim((0, 10))\n",
    "#     plt.draw()\n",
    "    # plt.pause(0.05)\n",
    "\n",
    "np.random.seed(21)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n  \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<svg xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"375.02pt\" height=\"284.012pt\" viewBox=\"0 0 375.02 284.012\" xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\">\n <metadata>\n  <rdf:RDF xmlns:dc=\"http://purl.org/dc/elements/1.1/\" xmlns:cc=\"http://creativecommons.org/ns#\" xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\">\n   <cc:Work>\n    <dc:type rdf:resource=\"http://purl.org/dc/dcmitype/StillImage\"/>\n    <dc:date>2022-10-18T11:11:34.814052</dc:date>\n    <dc:format>image/svg+xml</dc:format>\n    <dc:creator>\n     <cc:Agent>\n      <dc:title>Matplotlib v3.6.1, https://matplotlib.org/</dc:title>\n     </cc:Agent>\n    </dc:creator>\n   </cc:Work>\n  </rdf:RDF>\n </metadata>\n <defs>\n  <style type=\"text/css\">*{stroke-linejoin: round; stroke-linecap: butt}</style>\n </defs>\n <g id=\"figure_1\">\n  <g id=\"patch_1\">\n   <path d=\"M 0 284.012 \nL 375.02 284.012 \nL 375.02 0 \nL 0 0 \nz\n\" style=\"fill: #ffffff\"/>\n  </g>\n  <g id=\"axes_1\">\n   <g id=\"patch_2\">\n    <path d=\"M 10.7 273.312 \nL 367.82 273.312 \nL 367.82 7.2 \nL 10.7 7.2 \nz\n\" style=\"fill: #ffffff\"/>\n   </g>\n   <g id=\"matplotlib.axis_1\"/>\n   <g id=\"matplotlib.axis_2\"/>\n   <g id=\"line2d_1\">\n    <path d=\"M 189.26 273.312 \nL 179.360399 246.864898 \n\" clip-path=\"url(#pfe240cf282)\" style=\"fill: none; stroke: #000000; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"line2d_2\">\n    <path d=\"M 179.360399 246.864898 \n\" clip-path=\"url(#pfe240cf282)\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n    <defs>\n     <path id=\"m564146066c\" d=\"M -7.5 7.5 \nL 7.5 7.5 \nL 7.5 -7.5 \nL -7.5 -7.5 \nz\n\" style=\"stroke: #000000; stroke-linejoin: miter\"/>\n    </defs>\n    <g clip-path=\"url(#pfe240cf282)\">\n     <use xlink:href=\"#m564146066c\" x=\"179.360399\" y=\"246.864898\" style=\"fill-opacity: 0; stroke: #000000; stroke-linejoin: miter\"/>\n    </g>\n   </g>\n   <g id=\"line2d_3\">\n    <path d=\"M 189.26 273.312 \nL 199.159601 246.864898 \n\" clip-path=\"url(#pfe240cf282)\" style=\"fill: none; stroke: #000000; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"line2d_4\">\n    <path d=\"M 199.159601 246.864898 \nL 199.159601 220.253698 \n\" clip-path=\"url(#pfe240cf282)\" style=\"fill: none; stroke: #000000; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"line2d_5\">\n    <path d=\"M 199.159601 220.253698 \n\" clip-path=\"url(#pfe240cf282)\" style=\"fill: none; stroke: #ff7f0e; stroke-width: 1.5; stroke-linecap: square\"/>\n    <defs>\n     <path id=\"m8998335b62\" d=\"M 0 -7.5 \nL -6.495191 -3.75 \nL -6.495191 3.75 \nL -0 7.5 \nL 6.495191 3.75 \nL 6.495191 -3.75 \nz\n\" style=\"stroke: #000000; stroke-linejoin: miter\"/>\n    </defs>\n    <g clip-path=\"url(#pfe240cf282)\">\n     <use xlink:href=\"#m8998335b62\" x=\"199.159601\" y=\"220.253698\" style=\"fill-opacity: 0; stroke: #000000; stroke-linejoin: miter\"/>\n    </g>\n   </g>\n   <g id=\"line2d_6\">\n    <path d=\"M 199.159601 246.864898 \nL 218.836712 220.908065 \n\" clip-path=\"url(#pfe240cf282)\" style=\"fill: none; stroke: #000000; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"line2d_7\">\n    <path d=\"M 218.836712 220.908065 \nL 228.736313 194.460963 \n\" clip-path=\"url(#pfe240cf282)\" style=\"fill: none; stroke: #000000; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"line2d_8\">\n    <path d=\"M 228.736313 194.460963 \nL 228.736313 167.849763 \n\" clip-path=\"url(#pfe240cf282)\" style=\"fill: none; stroke: #000000; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"line2d_9\">\n    <path d=\"M 228.736313 167.849763 \nL 218.836712 141.40266 \n\" clip-path=\"url(#pfe240cf282)\" style=\"fill: none; stroke: #000000; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"line2d_10\">\n    <path d=\"M 218.836712 141.40266 \nL 199.159601 115.445827 \n\" clip-path=\"url(#pfe240cf282)\" style=\"fill: none; stroke: #000000; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"line2d_11\">\n    <path d=\"M 199.159601 115.445827 \n\" clip-path=\"url(#pfe240cf282)\" style=\"fill: none; stroke: #2ca02c; stroke-width: 1.5; stroke-linecap: square\"/>\n    <g clip-path=\"url(#pfe240cf282)\">\n     <use xlink:href=\"#m8998335b62\" x=\"199.159601\" y=\"115.445827\" style=\"fill-opacity: 0; stroke: #000000; stroke-linejoin: miter\"/>\n    </g>\n   </g>\n   <g id=\"line2d_12\">\n    <path d=\"M 218.836712 141.40266 \nL 218.836712 114.79146 \n\" clip-path=\"url(#pfe240cf282)\" style=\"fill: none; stroke: #000000; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"line2d_13\">\n    <path d=\"M 218.836712 114.79146 \n\" clip-path=\"url(#pfe240cf282)\" style=\"fill: none; stroke: #d62728; stroke-width: 1.5; stroke-linecap: square\"/>\n    <g clip-path=\"url(#pfe240cf282)\">\n     <use xlink:href=\"#m564146066c\" x=\"218.836712\" y=\"114.79146\" style=\"fill-opacity: 0; stroke: #000000; stroke-linejoin: miter\"/>\n    </g>\n   </g>\n   <g id=\"line2d_14\">\n    <path d=\"M 228.736313 167.849763 \nL 238.635914 141.40266 \n\" clip-path=\"url(#pfe240cf282)\" style=\"fill: none; stroke: #000000; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"line2d_15\">\n    <path d=\"M 238.635914 141.40266 \n\" clip-path=\"url(#pfe240cf282)\" style=\"fill: none; stroke: #9467bd; stroke-width: 1.5; stroke-linecap: square\"/>\n    <defs>\n     <path id=\"m462c0c1d2a\" d=\"M 0 -7.5 \nL -1.683855 -2.317627 \nL -7.132924 -2.317627 \nL -2.724534 0.885255 \nL -4.408389 6.067627 \nL -0 2.864745 \nL 4.408389 6.067627 \nL 2.724534 0.885255 \nL 7.132924 -2.317627 \nL 1.683855 -2.317627 \nz\n\" style=\"stroke: #000000; stroke-linejoin: bevel\"/>\n    </defs>\n    <g clip-path=\"url(#pfe240cf282)\">\n     <use xlink:href=\"#m462c0c1d2a\" x=\"238.635914\" y=\"141.40266\" style=\"fill-opacity: 0; stroke: #000000; stroke-linejoin: bevel\"/>\n    </g>\n   </g>\n   <g id=\"line2d_16\">\n    <path d=\"M 228.736313 194.460963 \nL 248.413423 168.50413 \n\" clip-path=\"url(#pfe240cf282)\" style=\"fill: none; stroke: #000000; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"line2d_17\">\n    <path d=\"M 248.413423 168.50413 \n\" clip-path=\"url(#pfe240cf282)\" style=\"fill: none; stroke: #8c564b; stroke-width: 1.5; stroke-linecap: square\"/>\n    <g clip-path=\"url(#pfe240cf282)\">\n     <use xlink:href=\"#m462c0c1d2a\" x=\"248.413423\" y=\"168.50413\" style=\"fill-opacity: 0; stroke: #000000; stroke-linejoin: bevel\"/>\n    </g>\n   </g>\n   <g id=\"line2d_18\">\n    <path d=\"M 218.836712 220.908065 \nL 248.048654 195.761627 \n\" clip-path=\"url(#pfe240cf282)\" style=\"fill: none; stroke: #000000; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"line2d_19\">\n    <path d=\"M 248.048654 195.761627 \n\" clip-path=\"url(#pfe240cf282)\" style=\"fill: none; stroke: #e377c2; stroke-width: 1.5; stroke-linecap: square\"/>\n    <g clip-path=\"url(#pfe240cf282)\">\n     <use xlink:href=\"#m462c0c1d2a\" x=\"248.048654\" y=\"195.761627\" style=\"fill-opacity: 0; stroke: #000000; stroke-linejoin: bevel\"/>\n    </g>\n   </g>\n   <g id=\"patch_3\">\n    <path d=\"M 10.7 273.312 \nL 10.7 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_4\">\n    <path d=\"M 367.82 273.312 \nL 367.82 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_5\">\n    <path d=\"M 10.7 273.312 \nL 367.82 273.312 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_6\">\n    <path d=\"M 10.7 7.2 \nL 367.82 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"pfe240cf282\">\n   <rect x=\"10.7\" y=\"7.2\" width=\"357.12\" height=\"266.112\"/>\n  </clipPath>\n </defs>\n</svg>\n",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "vee()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Recursion intro: the details (35 min)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- We are going to take a _very_ step-by-step approach to recursion.\n",
    "- It might be boring in the middle, but it's going somewhere."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Step 1: functions with outputs but no inputs\n",
    "\n",
    "Consider this function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def h():\n",
    "    return 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can call it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "h()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's add a function `g` that calls `h`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def g():\n",
    "    return h() + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- What's happening here? `g` is calling `h`, which returns $0$.\n",
    "- It then adds this result, $0$, to $1$ and gets $1$.\n",
    "- So it returns $1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's add a function `f` that calls `g`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f():\n",
    "    return g() + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- What's happening here? `f` is calling `g`.\n",
    "- We already know `g` returns $1$, so no need to go through that again in ours heads (but Python does).\n",
    "- So `f` adds $1+1$, and returns $2$.\n",
    "\n",
    "What's the idea here? That functions can call each other, and we can methodically \"unpack\" what happens when they call each other. And furthermore, if we already know what `g` does, we can forget about the fact that it calls `h`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Step 2: functions with inputs but no outputs\n",
    "\n",
    "Now let's make it more interesting by letting the functions take arguments. Consider these functions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def h(n):\n",
    "    print(\"You called h with argument\", n)\n",
    "    print(\"Ending h with argument\", n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "You called h with argument 3\n",
      "Ending h with argument 3\n"
     ]
    }
   ],
   "source": [
    "h(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "You called h with argument 2\n",
      "Ending h with argument 2\n"
     ]
    }
   ],
   "source": [
    "h(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def g(n):\n",
    "    print(\"You called g with argument\", n)\n",
    "    h(n-1)\n",
    "    print(\"Ending g with argument\", n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "You called g with argument 1\n",
      "You called h with argument 0\n",
      "Ending h with argument 0\n",
      "Ending g with argument 1\n"
     ]
    }
   ],
   "source": [
    "g(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "You called g with argument 2\n",
      "You called h with argument 1\n",
      "Ending h with argument 1\n",
      "Ending g with argument 2\n"
     ]
    }
   ],
   "source": [
    "g(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "You called g with argument 3\n",
      "You called h with argument 2\n",
      "Ending h with argument 2\n",
      "Ending g with argument 3\n"
     ]
    }
   ],
   "source": [
    "g(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ok, now let's add another function, `f`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(n):\n",
    "    print(\"You called f with argument\", n)\n",
    "    g(n-1)\n",
    "    print(\"Ending f with argument\", n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "You called f with argument 5\n",
      "You called g with argument 4\n",
      "You called h with argument 3\n",
      "Ending h with argument 3\n",
      "Ending g with argument 4\n",
      "Ending f with argument 5\n"
     ]
    }
   ],
   "source": [
    "f(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "You called f with argument 10\n",
      "You called g with argument 9\n",
      "You called h with argument 8\n",
      "Ending h with argument 8\n",
      "Ending g with argument 9\n",
      "Ending f with argument 10\n"
     ]
    }
   ],
   "source": [
    "f(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "FYI (optional): what we're seeing above is a depiction of the functions' [call stack](https://en.wikipedia.org/wiki/Call_stack). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Step 3: functions with inputs _and_ outputs\n",
    "\n",
    "Above, each function is passing data _into_ the next function.\n",
    "\n",
    "Below, we try passing data _out_ of each function as well."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "def h(n):\n",
    "    print(\"Starting h with argument\", n)\n",
    "    value = 0\n",
    "    print(\"Ending h with value\", value)\n",
    "    return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Starting h with argument 5\n",
      "Ending h with value 0\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "h(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`h` is a weird function that ignores its input and just returns 0."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Below, `g` calls `h` will a smaller value of `n`, and then adds 1 to the result."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "def g(n):\n",
    "    print(\"Starting g with argument\", n)\n",
    "    value = h(n-1) + 1\n",
    "    print(\"Ending g with value\", value)\n",
    "    return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Starting g with argument 10\n",
      "Starting h with argument 9\n",
      "Ending h with value 0\n",
      "Ending g with value 1\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's look at the _order_ of the print statements:\n",
    "\n",
    "1. We start `g`\n",
    "2. We start `h`\n",
    "3. We end `h`\n",
    "4. We end `g`\n",
    "\n",
    "This is critical to understanding what happens next."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(n):\n",
    "    print(\"Starting f with argument\", n)\n",
    "    value = g(n-1) + 1\n",
    "    print(\"Ending f with value\", value)\n",
    "    return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Starting f with argument 11\n",
      "Starting g with argument 10\n",
      "Starting h with argument 9\n",
      "Ending h with value 0\n",
      "Ending g with value 1\n",
      "Ending f with value 2\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "result = f(11)\n",
    "result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's remove some of the print statements to make things more compact:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(n):\n",
    "    print(\"Starting f with argument\", n)\n",
    "    return g(n-1) + 1\n",
    "\n",
    "\n",
    "def g(n):\n",
    "    print(\"Starting g with argument\", n)\n",
    "    return h(n-1) + 1\n",
    "\n",
    "\n",
    "def h(n):\n",
    "    print(\"Starting h with argument\", n)\n",
    "    return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Starting f with argument 11\n",
      "Starting g with argument 10\n",
      "Starting h with argument 9\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(11)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So far, this isn't interesting because we're not using `n` for anything. We get the same result, $2$, for any value of `n`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Starting f with argument 1000\n",
      "Starting g with argument 999\n",
      "Starting h with argument 998\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now look at this code (we're getting close to the punch line):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(n):\n",
    "    print(\"Starting f with argument\", n)\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    else:\n",
    "        return g(n-1) + 1\n",
    "\n",
    "\n",
    "def g(n):\n",
    "    print(\"Starting g with argument\", n)\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    else:\n",
    "        return h(n-1) + 1\n",
    "\n",
    "\n",
    "def h(n):\n",
    "    print(\"Starting h with argument\", n)\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    else:\n",
    "        return i(n-1) + 1\n",
    "\n",
    "# ...\n",
    "# ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Starting f with argument 1\n",
      "Starting g with argument 0\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Starting g with argument 1\n",
      "Starting h with argument 0\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This code actually uses `n`. Here's what it `f` outputs\n",
    "\n",
    "|  `n`   |   `f(n)` |\n",
    "|--------|--------|\n",
    "| 0      |    0   |\n",
    "| 1      |    1   |\n",
    "| 2      |    2   |\n",
    "| 3+     | error  |\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Starting f with argument 0\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Starting f with argument 1\n",
      "Starting g with argument 0\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Starting f with argument 2\n",
      "Starting g with argument 1\n",
      "Starting h with argument 0\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Starting f with argument 3\n",
      "Starting g with argument 2\n",
      "Starting h with argument 1\n"
     ]
    },
    {
     "ename": "NameError",
     "evalue": "name 'i' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "Cell \u001b[0;32mIn [42], line 1\u001b[0m\n\u001b[0;32m----> 1\u001b[0m f(\u001b[39m3\u001b[39;49m)\n",
      "Cell \u001b[0;32mIn [36], line 6\u001b[0m, in \u001b[0;36mf\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[39mreturn\u001b[39;00m \u001b[39m0\u001b[39m\n\u001b[1;32m      5\u001b[0m \u001b[39melse\u001b[39;00m:\n\u001b[0;32m----> 6\u001b[0m     \u001b[39mreturn\u001b[39;00m g(n\u001b[39m-\u001b[39;49m\u001b[39m1\u001b[39;49m) \u001b[39m+\u001b[39m \u001b[39m1\u001b[39m\n",
      "Cell \u001b[0;32mIn [36], line 14\u001b[0m, in \u001b[0;36mg\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m     12\u001b[0m     \u001b[39mreturn\u001b[39;00m \u001b[39m0\u001b[39m\n\u001b[1;32m     13\u001b[0m \u001b[39melse\u001b[39;00m:\n\u001b[0;32m---> 14\u001b[0m     \u001b[39mreturn\u001b[39;00m h(n\u001b[39m-\u001b[39;49m\u001b[39m1\u001b[39;49m) \u001b[39m+\u001b[39m \u001b[39m1\u001b[39m\n",
      "Cell \u001b[0;32mIn [36], line 22\u001b[0m, in \u001b[0;36mh\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m     20\u001b[0m     \u001b[39mreturn\u001b[39;00m \u001b[39m0\u001b[39m\n\u001b[1;32m     21\u001b[0m \u001b[39melse\u001b[39;00m:\n\u001b[0;32m---> 22\u001b[0m     \u001b[39mreturn\u001b[39;00m i(n\u001b[39m-\u001b[39m\u001b[39m1\u001b[39m) \u001b[39m+\u001b[39m \u001b[39m1\u001b[39m\n",
      "\u001b[0;31mNameError\u001b[0m: name 'i' is not defined"
     ]
    }
   ],
   "source": [
    "f(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And now the key insight: all of the functions above are _exactly the same_. They check if `n` is zero. If so, they return zero. Otherwise, they call a function _identical to themselves_ with argument `n-1`, add `1` to the result, and return it.\n",
    "\n",
    "So why write"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(n):\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    else:\n",
    "        return g(n-1) + 1\n",
    "\n",
    "# def g(n):\n",
    "#     ...\n",
    "#\n",
    "# def h(n):\n",
    "#     ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "a million times when you can just write"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(n):\n",
    "    if n == 0:  # base case\n",
    "        return 0\n",
    "    else:\n",
    "        return f(n-1) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "BAM! Recursion. \n",
    "\n",
    "- It is just incidental that all the functions have the same name, `f`. \n",
    "- It may be helpful for you to think of them as separate. \n",
    "- They do live in separate universes, with separate variables, like `n` and all other variables. \n",
    "- The fact that they are all named `f` is just a matter of convenience, to avoid writing an infinite amount of code."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's put our print string back in..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(n):\n",
    "    print(\"Starting f with argument\", n)\n",
    "    if n == 0:\n",
    "        print(\"Ending f with n =\", n, \"and returning 0 (base case)\")\n",
    "        return 0\n",
    "    else:\n",
    "        value = f(n-1) + 1\n",
    "        print(\"Ending f with n =\", n, \"and returning\", value)\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Starting f with argument 2\n",
      "Starting f with argument 1\n",
      "Starting f with argument 0\n",
      "Ending f with n = 0 and returning 0 (base case)\n",
      "Ending f with n = 1 and returning 1\n",
      "Ending f with n = 2 and returning 2\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Does this look familiar? It's the same \"call stack\" we saw before with our `f`, `g`, and `h`. Except now all the functions are named `f`. \n",
    "- The `if n == 0` part of the code is called the _base case_. This is like the function `h` earlier. It is the function that does _not_ call itself, and it's what causes the recursion to terminate.\n",
    "- The call to itself, in this case `f(n-1)` is the recursive step."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Starting f with argument 5\n",
      "Starting f with argument 4\n",
      "Starting f with argument 3\n",
      "Starting f with argument 2\n",
      "Starting f with argument 1\n",
      "Starting f with argument 0\n",
      "Ending f with n = 0 and returning 0 (base case)\n",
      "Ending f with n = 1 and returning 1\n",
      "Ending f with n = 2 and returning 2\n",
      "Ending f with n = 3 and returning 3\n",
      "Ending f with n = 4 and returning 4\n",
      "Ending f with n = 5 and returning 5\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stack overflow"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img width=\"400\" src=\"https://upload.wikimedia.org/wikipedia/commons/thumb/0/02/Stack_Overflow_logo.svg/512px-Stack_Overflow_logo.svg.png\">\n",
    "\n",
    "(Image source: [Wikipedia](https://commons.wikimedia.org/wiki/File:Stack_Overflow_logo.svg))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- A stack overflow error most commonly occurs when a recursive function makes an exceedingly large numbers of calls to itself (usually because of not properly setting up a base case), causing the memory allocated for a function's call stack to overflow.\n",
    "\n",
    "- Python prevents this from happening by throwing a `RecursionError` when a certain number of recursive calls are made (this number is system-dependent):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "def inf_recursion(i):\n",
    "    print(\"i =\", i)\n",
    "    return inf_recursion(i + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# inf_recursion(1)  # will throw RecursionError"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Break (5 min)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary search, revisited (5 min)\n",
    "\n",
    "- Let's return to binary search from [Lecture 2](02_searching-sorting-hash.ipynb).\n",
    "- The code is rather messy.\n",
    "- Here is a case where recursion works beautifully."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_search(data, key):\n",
    "    \"\"\"\n",
    "    Searches the key in data using binary search. \n",
    "    Returns True if found and False otherwise. \n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    data : list\n",
    "        the elements to search within\n",
    "    key : int\n",
    "        the key to search for\n",
    "\n",
    "    Returns\n",
    "    -------\n",
    "    bool\n",
    "        is the key contained in the data?\n",
    "\n",
    "    Examples\n",
    "    --------\n",
    "    >>> binary_search([1, 7, 35, 45, 67], 3)\n",
    "    False\n",
    "    >>> binary_search([1, 7, 35, 45, 67], 7)\n",
    "    True\n",
    "    \"\"\"\n",
    "    if len(data) == 1:\n",
    "        return data[0] == key\n",
    "\n",
    "    mid = len(data)//2\n",
    "    if key < data[mid]:\n",
    "        return binary_search(data[:mid], key)\n",
    "    else:\n",
    "        return binary_search(data[mid:], key)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = [-12, 4, 7, 9, 45, 987, 987, 1000, 2000]\n",
    "\n",
    "# Test cases for binary search\n",
    "# key is the first element in the list\n",
    "assert binary_search(data, -12)\n",
    "\n",
    "# key is the last element in the list\n",
    "assert binary_search(data, 2000)\n",
    "\n",
    "# key is the middle element in the list\n",
    "assert binary_search(data, 45)\n",
    "\n",
    "# key occurs multiple times in the list\n",
    "assert binary_search(data, 987)\n",
    "\n",
    "# key is larger than the largest element in the list\n",
    "assert not binary_search(data, 3000)\n",
    "\n",
    "# key is smaller than the smallest element in the list\n",
    "assert not binary_search(data, -18)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- So elegant!\n",
    "- And also maps more clearly to our verbal description of the algorithm (think of the phone book)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Multiple recursive calls (20 min)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider the function below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(n):\n",
    "    if n == 1 or n == 2:\n",
    "        return 1\n",
    "    else: \n",
    "        return f(n-1) + f(n-2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What is returned by `f(3)`?\n",
    "What is returned by `f(4)`?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(n):\n",
    "    print(\"Starting f with argument\", n)\n",
    "    if n == 1 or n == 2:\n",
    "        return 1\n",
    "    else:\n",
    "        return f(n-1) + f(n-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Starting f with argument 4\n",
      "Starting f with argument 3\n",
      "Starting f with argument 2\n",
      "Starting f with argument 1\n",
      "Starting f with argument 2\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note this is equivalent to:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(n):\n",
    "    print(\"Starting f with argument\", n)\n",
    "    if n == 1 or n == 2:\n",
    "        return 1\n",
    "    val1 = f(n-1)\n",
    "    val2 = f(n-2)\n",
    "    return val1 + val2\n",
    "\n",
    "f(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In other words, there's no significance to the two recursive calls being on the same line of code."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's draw out the execution tree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- First, `f(4)` is called.\n",
    "- The first thing it does is call `f(n-1) = f(3)`\n",
    "\n",
    "```\n",
    "            f(4)\n",
    "           /     \n",
    "        f(3)  \n",
    "```\n",
    "\n",
    "\n",
    "- The first thing `f(3)` does is call `f(n-1)=f(2)`.\n",
    "\n",
    "\n",
    "```\n",
    "            f(4)\n",
    "           /    \n",
    "        f(3)  \n",
    "        /   \n",
    "     f(2)  \n",
    "```\n",
    "\n",
    "- `f(2)` triggers the base case and immediately returns $1$.\n",
    "\n",
    "\n",
    "```\n",
    "            f(4)\n",
    "           /    \n",
    "        f(3)  \n",
    "        /1    \n",
    "     f(2)=1  \n",
    "```\n",
    "\n",
    "- The return value $1$ is passed back up to `f(3)`. \n",
    "- `f(3)` is trying to call `f(n-1) + f(n-2)`, and the first of those has just returned with value $1$.\n",
    "- So it now proceeds to call the second one, namely `f(n-2)` or `f(1)`.\n",
    "\n",
    "\n",
    "```\n",
    "            f(4)\n",
    "           /      \n",
    "         f(3)  \n",
    "        /1   \\\n",
    "     f(2)=1  f(1)\n",
    "```\n",
    "\n",
    "- `f(1)` triggers the base case and immediately returns $1$.\n",
    "- The return value $1$ is passed back up to `f(3)`. \n",
    "\n",
    "\n",
    "```\n",
    "            f(4)\n",
    "           /     \n",
    "         f(3)\n",
    "        /1   \\1\n",
    "     f(2)=1  f(1)=1         \n",
    "```\n",
    "\n",
    "- `f(3)` is now done, because it has computed $f(n-1) + f(n-2) = 1 + 1 = 2$\n",
    "\n",
    "\n",
    "```\n",
    "            f(4)\n",
    "           /2      \n",
    "         f(3)=2 \n",
    "        /1   \\1\n",
    "     f(2)=1  f(1)=1         \n",
    "```\n",
    "\n",
    "- It passes this value, $2$ up to its caller, namely `f(4)`.\n",
    "- `f(4)` is trying to call `f(n-1) + f(n-2)`, and the first of those has just returned with value $2$.\n",
    "- So it now proceeds to call the second one, namely `f(n-2)` or `f(2)`.\n",
    "\n",
    "\n",
    "```\n",
    "             f(4)\n",
    "           /2    \\ \n",
    "        f(3)=2  f(2)\n",
    "        /1   \\1\n",
    "     f(2)=1  f(1)=1         \n",
    "```\n",
    "\n",
    "- `f(2)` triggers the base case and immediately returns $1$.\n",
    "\n",
    "\n",
    "```\n",
    "             f(4)\n",
    "           /2    \\1 \n",
    "        f(3)=2  f(2)=1\n",
    "        /1   \\1\n",
    "     f(2)=1  f(1)=1         \n",
    "```\n",
    "\n",
    "- `f(4)` is now done, because it has computed $f(n-1) + f(n-2) = 2 + 1 = 3$\n",
    "\n",
    "\n",
    "```\n",
    "            f(4)=3\n",
    "           /2    \\1\n",
    "        f(3)=2  f(2)=1\n",
    "        /1   \\1\n",
    "     f(2)=1  f(1)=1         \n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- The function above implements the [Fibonacci sequence](https://en.wikipedia.org/wiki/Fibonacci_number): $F_n=F_{n-1}+F_{n-2}$.\n",
    "\n",
    "- In this case we need 2 base cases to get things started, because $F_n$ depends on the previous 2 steps.\n",
    "- Recursive functions don't need to be sequences, as we'll see.\n",
    "- The time complexity here is something like $O(2^n)$ \n",
    "  - (Slightly less than $2^n$ steps but close enough.)\n",
    "  - It is generally true, rougly speaking, that if a recursive function calls itself $k$ times and the \"depth\" of the recursion is $n$, then the time complexity is $k^n$. More on this next class.\n",
    "- This is not a good implementation for the Fibonacci numbers!\n",
    "  - More on this in lecture 8."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Revisiting the binary search code above:\n",
    "\n",
    "```python\n",
    "def binary_search(data, key):\n",
    "    if len(data) == 1:\n",
    "        return data[0] == key   \n",
    "\n",
    "    mid = len(data)//2\n",
    "    if key < data[mid]:\n",
    "        return binary_search(data[:mid], key)\n",
    "    else:\n",
    "        return binary_search(data[mid:], key)\n",
    "```\n",
    "\n",
    "**Question:** Is this function making multiple recursive calls and thus running in $O(2^n)$ time?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br><br><br><br><br>\n",
    "**Answer:** No! Because of the `if/else`, it's only calling itself once.\n",
    "\n",
    "- Does that mean it runs in $O(n)$ time?\n",
    "- No, in fact, it runs in $O(\\log n)$ because it calls itself on a list of 1/2 the size each time. \n",
    "  - We discussed this last class.\n",
    "- We can't just read off the running time from the code without thinking carefully about it."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.10.6 ('dsci512')",
   "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.6"
  },
  "vscode": {
   "interpreter": {
    "hash": "833530e805897aab5e7a30ee530b0bcb4cd19373b840f29eae5897b61b26002e"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}