{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "fdcf04c6",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Recursion\n",
    "\n",
    "**CS 66: Introduction to Computer Science II**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fa72fac7",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## References for this lecture\n",
    "\n",
    "Problem Solving with Algorithms and Data Structures using Python\n",
    "\n",
    "Sections 5.1-5.8 [https://runestone.academy/ns/books/published/pythonds/Recursion/toctree.html](https://runestone.academy/ns/books/published/pythonds/Recursion/toctree.html)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d684528c",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Wrapping up Hash Tables\n",
    "\n",
    "The hash tables we made will only store integers\n",
    "\n",
    "Can you think of a strategy that will allow us to put strings in a table?\n",
    "\n",
    "```\n",
    "0:[]\n",
    "1:[]\n",
    "2:[]\n",
    "3:['Dr. Mario']\n",
    "4:[]\n",
    "5:['Pikachu', 'Kirby']\n",
    "6:['Sheik', 'Mr. Game and Watch']\n",
    "7:['Dr. Carlson', 'Jiggly Puff']\n",
    "8:['Captain Falcon']\n",
    "9:['Mew Two']\n",
    "```\n",
    "\n",
    "\n",
    "_these are the names my kids gave our chicks that just hatched_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3ae4c187",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "0059d978",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Built-in Hash Function\n",
    "\n",
    "Python contains a built-in hash function that you can use.\n",
    "\n",
    "Be careful, the hash is somewhat randomized and values change every time you re-start your code (this brings issues with saving hashed values to a file, etc.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ba82f601",
   "metadata": {},
   "outputs": [],
   "source": [
    "print( hash(\"Star Wars: Episode VII - The Force Awakens (2015)\") )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7ba72034",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Map ADT\n",
    "\n",
    "Hash tables are also often used to implement the __map__ abstract data type\n",
    "\n",
    "A __map__ abstract data type stores _key-value_ pairs and allows you to use a _key_ to look up its associated _value_.\n",
    "\n",
    "A Python dictionary is a map.\n",
    "\n",
    "There are other data structures you could use to implement a map, such as a list of tuples.\n",
    "\n",
    "The following is the book's definition of the Map ADT:\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bac37f0b",
   "metadata": {},
   "source": [
    "* `Map()` Create a new, empty map. It returns an empty map collection.\n",
    "* `put(key,val)` Add a new key-value pair to the map. If the key is already in the map then replace the old value with the new value.\n",
    "* `get(key)` Given a key, return the value stored in the map or `None` otherwise.\n",
    "* `del` Delete the key-value pair from the map using a statement of the form `del map[key]`.\n",
    "* `len()` Return the number of key-value pairs stored in the map.\n",
    "* `in` Return True for a statement of the form key in map, if the given key is in the map, False otherwise.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "53041395",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Chained Hash Map\n",
    "\n",
    "We could use a similar strategy that we used for set, but store _(key,value)_ tuples\n",
    "\n",
    "```\n",
    "0:[(20, 'chicken')]\n",
    "1:[(31, 'cow')]\n",
    "2:[]\n",
    "3:[(93, 'lion')]\n",
    "4:[(54, 'cat'), (44, 'goat')]\n",
    "5:[(55, 'pig')]\n",
    "6:[(26, 'dog')]\n",
    "7:[(17, 'tiger'), (77, 'bird')]\n",
    "8:[]\n",
    "9:[]\n",
    "```\n",
    "\n",
    "(maybe this is a map that a zoo uses to look up which animal has each id)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1135be9b",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Textbook's Linear-Probed-Hash-Table Map\n",
    "\n",
    "The following code shows the start of the book's approach to using a Hash Table with linear probing to implement a map.\n",
    "\n",
    "`self.slots` list stores the keys\n",
    "\n",
    "`self.data` stores the associated values\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "695dff28",
   "metadata": {},
   "outputs": [],
   "source": [
    "class HashTable:\n",
    "    def __init__(self):\n",
    "        self.size = 11\n",
    "        self.slots = [None] * self.size\n",
    "        self.data = [None] * self.size\n",
    "        \n",
    "    def put(self,key,data):\n",
    "        hashvalue = self.hashfunction(key,len(self.slots))\n",
    "\n",
    "        if self.slots[hashvalue] == None:\n",
    "            self.slots[hashvalue] = key\n",
    "            self.data[hashvalue] = data\n",
    "        else:\n",
    "            if self.slots[hashvalue] == key:\n",
    "                self.data[hashvalue] = data  #replace\n",
    "            else:\n",
    "                nextslot = self.rehash(hashvalue,len(self.slots))\n",
    "            while self.slots[nextslot] != None and self.slots[nextslot] != key:\n",
    "                nextslot = self.rehash(nextslot,len(self.slots))\n",
    "\n",
    "            if self.slots[nextslot] == None:\n",
    "                self.slots[nextslot]=key\n",
    "                self.data[nextslot]=data\n",
    "            else:\n",
    "                self.data[nextslot] = data #replace\n",
    "\n",
    "    def hashfunction(self,key,size):\n",
    "         return key%size\n",
    "\n",
    "    def rehash(self,oldhash,size):\n",
    "        return (oldhash+1)%size"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "baa36b8c",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Recursion\n",
    "\n",
    "a __recursive__ function is a function that calls itself.\n",
    "\n",
    "Recursion is also a _problem solving strategy_ that allows you to solve problems by breaking them down to smaller and smaller sub-problems, which are eventually _trivial_ to solve.\n",
    "\n",
    "It can be hard to think recursively at first, but when you get good at it, it will allow you to solve some problems in really elegant ways."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b593aa60",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Group Activity Problem 1\n",
    "\n",
    "Copy this function into a `.py` file and run it. It will eventually result in an error - _wait for it_. \n",
    "\n",
    "Read the error message you get. Discuss in your groups:\n",
    "\n",
    "1. What is the difference between this and an infinite loop?\n",
    "2. Why did this result in an error when an infinite loop would just go on forever?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d9b43723",
   "metadata": {},
   "outputs": [],
   "source": [
    "def recursive_hello():\n",
    "    print(\"hello\")\n",
    "    recursive_hello()\n",
    "    \n",
    "recursive_hello()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c9a92f5f",
   "metadata": {},
   "source": [
    "Then try this version:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6d52c3e1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def recursive_hello(n):\n",
    "    if n > 0:\n",
    "        print(\"hello\")\n",
    "        recursive_hello(n-1)\n",
    "        \n",
    "recursive_hello(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ff1a553d",
   "metadata": {},
   "source": [
    "Discuss:\n",
    "\n",
    "3. What causes this one to stop when the first version didn't?\n",
    "4. What does the parameter, `n` do in this version?\n",
    "5. Why did the programmer put `n-1` in for the argument in the recursive call?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a2131e79",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Recursive problem solving example\n",
    "\n",
    "Let's revisit the sum-of-n problem we previously solved in different ways. The goal is to write a function that will compute \n",
    "\n",
    "$$1+2+3+\\cdots+(n-1)+n$$\n",
    "\n",
    "We might start by breaking $1+2+3+\\cdots+(n-1)+n$ into two parts:\n",
    "\n",
    "$$1+2+3+\\cdots+(n-1)$$\n",
    "\n",
    "and\n",
    "\n",
    "$$n$$\n",
    "\n",
    "Notice that $1+2+3+\\cdots+(n-1)$ is just a smaller version of the original problem! So, a recursive solution might look like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "67ba669c",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def sum_of_n(n):\n",
    "    result = sum_of_n(n-1) + n\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "22571d22",
   "metadata": {},
   "source": [
    "There's a problem: this one has no way to stop. \n",
    "\n",
    "To get it to stop, we need to think about what our __base case__ - the smallest case, when the problem is simple. For sum-of-n, it could be when n is 0.\n",
    "\n",
    "The sum of all numbers up to 0 is just 0, so we add this into our code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6eee2688",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def sum_of_n(n):\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    else:\n",
    "        result = sum_of_n(n-1) + n\n",
    "        return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "27af7347",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## The Three Laws of Recursion\n",
    "\n",
    "1. A recursive algorithm must have a base case.\n",
    "2. A recursive algorithm must change its state and move toward the base case.\n",
    "3. A recursive algorithm must call itself, recursively.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "88d7aa23",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Group Activity Problem 2\n",
    "\n",
    "The factorial of a number (often denoted in math as $n!$) is defined as \n",
    "\n",
    "$$ n! = 1 * 2 * 3 * \\cdots * (n-1) * n $$\n",
    "\n",
    "Here's some code which attempts to solve it recursively, but it is missing a base case. Discuss what the base case should be, and then add it to the code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ebdcf376",
   "metadata": {},
   "outputs": [],
   "source": [
    "def factorial(n):\n",
    "    result = n * factorial(n-1)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d49de903",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Group Activity Problem 3\n",
    "\n",
    "The following is an approach to finding the sum of a list of numbers. The idea that this programmer came up with is to notice that the sum of a list like `[1,3,5,7,9]` is the same as `1` plus the sum of `[3,5,7,9]`. The base case happens when there is only one item in the list. The programmer has written part of this but is stuck on the recursive call. Fill in the blank for them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e4d38e7d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def listsum(num_list):\n",
    "    if len(num_list) == 1:\n",
    "        return num_list[0]\n",
    "    else:\n",
    "        return num_list[0] + #fill in the blank"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "15c1fba9",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Group Activity Problem 4\n",
    "\n",
    "The code below is a variation of the `UnorderedList` implementation we've been working on, except the `search` function has been replaced with a new recursive version. Run the code and make sure it works, then answer the following questions:\n",
    "\n",
    "1. There's more than one base case - what are they?\n",
    "2. Notice that the `__search_node` method has a parameter called `currnode`. What is `currnode` and why does it have to be a parameter?\n",
    "3. Why is there both a `search` and a `__search_node` method? Why do you think `__search_node` has been named with two underscores?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d761b982",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self,initdata):\n",
    "        self.data = initdata\n",
    "        self.next = None\n",
    "\n",
    "    def getData(self):\n",
    "        return self.data\n",
    "\n",
    "    def getNext(self):\n",
    "        return self.next\n",
    "\n",
    "    def setData(self,newdata):\n",
    "        self.data = newdata\n",
    "\n",
    "    def setNext(self,newnext):\n",
    "        self.next = newnext\n",
    "\n",
    "class UnorderedList:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        self.length = 0\n",
    "        \n",
    "    def isEmpty(self):\n",
    "        return self.head == None\n",
    "        \n",
    "    def size(self):\n",
    "        return self.length\n",
    "\n",
    "    #this method is really a prepend - it puts the new node at the beginning\n",
    "    def add(self,item):\n",
    "        temp = Node(item)\n",
    "        temp.setNext(self.head)\n",
    "        self.head = temp\n",
    "        self.length += 1\n",
    "            \n",
    "    def __repr__(self):\n",
    "        list_representation = \"\"\n",
    "        current = self.head #start with the Node at the head\n",
    "        while current: #this will keep going until current equals None\n",
    "            list_representation += str(current.getData())+\" -> \"\n",
    "            current = current.getNext() #move on to the next Node in the list\n",
    "        list_representation += \"None\" #the last one in the list points to None\n",
    "        return list_representation\n",
    "\n",
    "    def __contains__(self,item):\n",
    "        return self.search(item)\n",
    "    \n",
    "    ############################\n",
    "    ### New code starts here ###\n",
    "    ############################\n",
    "    \n",
    "    def search(self,item):\n",
    "        return self.__search_node(item,self.head)\n",
    "    \n",
    "    def __search_node(self,item,currnode):\n",
    "        #if we're at the end of the list return False - it isn't here\n",
    "        if currnode == None:\n",
    "            return False\n",
    "        #we found the item - return True\n",
    "        elif currnode.getData() == item:\n",
    "            return True\n",
    "        #search the rest of the list\n",
    "        else:\n",
    "            return self.__search_node(item,currnode.getNext())\n",
    "        \n",
    "\n",
    "\n",
    "my_list = UnorderedList()\n",
    "\n",
    "my_list.add(31)\n",
    "my_list.add(77)\n",
    "my_list.add(17)\n",
    "my_list.add(93)\n",
    "my_list.add(26)\n",
    "my_list.add(54)\n",
    "\n",
    "print( my_list.search(17) )\n",
    "print( my_list.search(13) )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c91b5860",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Group Activity Problem 5\n",
    "\n",
    "You can write an `index` method which calls a recursive `__index_node` method in a similar way to `search` and `__search_node`. What changes would you need to make for that to work?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d873ef77",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Turtle Graphics\n",
    "\n",
    "The turtle graphics package is a fun way to create drawings by giving commands that describe how a pencil (or a turtle) should move around on a piece of paper.\n",
    "\n",
    "Documentation: https://docs.python.org/3/library/turtle.html\n",
    "\n",
    "Example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b43e7c5e",
   "metadata": {},
   "outputs": [],
   "source": [
    "import turtle\n",
    "\n",
    "my_turtle = turtle.Turtle()\n",
    "my_win = turtle.Screen()\n",
    "\n",
    "my_turtle.forward(100)\n",
    "my_turtle.right(90)\n",
    "my_turtle.forward(50)\n",
    "my_turtle.right(45)\n",
    "my_turtle.forward(200)\n",
    "my_turtle.left(30)\n",
    "my_turtle.forward(50)\n",
    "\n",
    "turtle.exitonclick()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aecba899",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "## Group Activity Problem 6\n",
    "\n",
    "Write some additional turtle instructions to see if you can it to move back where it started."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "46b11dfa",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Group Activity Problem 7\n",
    "\n",
    "Run the following recursive function which draws a spiral. Discuss in your groups: \n",
    "\n",
    "1. What does the `90` do?\n",
    "2. What does it include `lineLen-5`?\n",
    "3. What is the base case of this recursive function?\n",
    "\n",
    "Then, change the `90` to `45`. What does that do? Can you adjust the code to make the spiral look like a smooth curve?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a79a26e8",
   "metadata": {},
   "outputs": [],
   "source": [
    "import turtle\n",
    "\n",
    "myTurtle = turtle.Turtle()\n",
    "myWin = turtle.Screen()\n",
    "\n",
    "def drawSpiral(myTurtle, lineLen):\n",
    "    if lineLen > 0:\n",
    "        myTurtle.forward(lineLen)\n",
    "        myTurtle.right(90)\n",
    "        drawSpiral(myTurtle,lineLen-5)\n",
    "\n",
    "drawSpiral(myTurtle,100)\n",
    "myWin.exitonclick()"
   ]
  }
 ],
 "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.10.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}