6_Algorithms_Recursion.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "ein.tags": [
     "worksheet-0"
    ],
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "# Algorithms #\n",
    "## Why do we need Algorithms? ##\n",
    "Algorithms is a set of instructions to have the computer do stuff. In algorithms, we attempt to make the algorithm run as fast as possible **given constraints**\n",
    "\n",
    "Over the next 2 weeks, you will learn about how to analyze algorithms and be comfortable deriving algorithms.\n",
    "\n",
    "## Types Of Algorithms ##\n",
    "Here are some various topics (not all)\n",
    "* Algorithms Built for Speed\n",
    "* Algorithms Built to Save Space\n",
    "* Algorithms for Specific Data Structures\n",
    "* Algorithms for Infinite Computing Power\n",
    "* Algorithms for Infinite Threads\n",
    "* Algorithms with Best **Theoretical** Guarentees\n",
    "* Algorithms for Quantum Computing\n",
    "* P vs NP\n",
    "\n",
    "But wait, why isn't the algorithm with the best theoretical guarentee the fastest?\n",
    "How do we judge how good an algorithm is?\n",
    "\n",
    "## Theory vs Real World ##\n",
    "When we come up with algorithms, we typically do not take advantage of hardware specific optimizations.\n",
    "1. Vectorization\n",
    " - **Simple** operations done in parallel (NOT MULTITHREADING!)\n",
    "2. Cache Performance\n",
    " - Loop Unrolling\n",
    " - Linear, more predictable algorithms perform much better\n",
    "3. Multithreading\n",
    " - Mutual Exclusivity\n",
    " - \"Embarassing Parallel\" Problems\n",
    "\n",
    "Despite the split between real world problems vs theoretical problems vs hardware problems, all of these use one common stratergy...\n",
    "\n",
    "Recursion!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "ein.tags": [
     "worksheet-0"
    ],
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "# Recursion #\n",
    "Formally, **recursion** is when there is repetition: there is a subproblem to itself.\n",
    "We call a function **recursive** when it calls itself. This is what Computer Scientists refer to as **recursion**.\n",
    "\n",
    "Inuitively, it actually works more like the folowing:\n",
    "\n",
    "What does recursion mean? It means (recursion-1). Which means (recursion-2). Which means...\n",
    "\n",
    "This repeats until some person eventually solves it for us.\n",
    "\n",
    "# Example: Basic Recursion #"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "autoscroll": "json-false",
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "ein.tags": [
     "worksheet-0"
    ],
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m\u001b[0m",
      "\u001b[0;31mKeyboardInterrupt\u001b[0mTraceback (most recent call last)",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      5\u001b[0m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 7\u001b[0;31m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-02a320665100>\u001b[0m in \u001b[0;36mhello_recursion\u001b[0;34m()\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mtime\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      2\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0.5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Pauses instruction for 0.5 second\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"hello recursion!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m     \u001b[0;32mreturn\u001b[0m \u001b[0mhello_recursion\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "hello recursion!\n",
      "hello recursion!\n",
      "hello recursion!\n",
      "hello recursion!\n",
      "hello recursion!\n",
      "hello recursion!\n",
      "hello recursion!\n",
      "hello recursion!\n",
      "hello recursion!\n",
      "hello recursion!\n",
      "hello recursion!\n",
      "hello recursion!\n",
      "hello recursion!\n",
      "hello recursion!\n",
      "hello recursion!\n",
      "hello recursion!\n",
      "hello recursion!\n",
      "hello recursion!\n",
      "hello recursion!\n",
      "hello recursion!\n",
      "hello recursion!\n",
      "hello recursion!\n",
      "hello recursion!\n",
      "hello recursion!\n",
      "hello recursion!\n",
      "hello recursion!\n",
      "hello recursion!\n",
      "hello recursion!\n",
      "hello recursion!\n",
      "hello recursion!\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "def hello_recursion():\n",
    "    time.sleep(0.5) # Pauses instruction for 0.5 second\n",
    "    print(\"hello recursion!\")\n",
    "    return hello_recursion()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "ein.tags": [
     "worksheet-0"
    ],
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "What happens when you run `hello_recursion()`?\n",
    "\n",
    "Hint: You can interrupt the kernel if you get stuck."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "ein.tags": [
     "worksheet-0"
    ],
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "# Base Cases #\n",
    "So we ran `hello_recursion()`, but it never terminated! This is why we need a base case.\n",
    "\n",
    "A base case is when we tell the computer to stop evaluating cases and continue!\n",
    "So if we wanted to print `n` messages, our `hello_recursion` should be structured differently."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "autoscroll": "json-false",
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "ein.tags": [
     "worksheet-0"
    ],
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Hello Recursion! : 10\n",
      "Hello Recursion! : 9\n",
      "Hello Recursion! : 8\n",
      "Hello Recursion! : 7\n",
      "Hello Recursion! : 6\n",
      "Hello Recursion! : 5\n",
      "Hello Recursion! : 4\n",
      "Hello Recursion! : 3\n",
      "Hello Recursion! : 2\n",
      "Hello Recursion! : 1\n",
      "Hello Base Case! : 0\n"
     ]
    }
   ],
   "source": [
    "def hello_recursion(n):\n",
    "    if n <= 0:\n",
    "        print(\"Hello Base Case! : %d\" % (n))\n",
    "        return\n",
    "    \n",
    "    print(\"Hello Recursion! : %d\" % (n))\n",
    "    return hello_recursion(n-1)\n",
    "\n",
    "hello_recursion(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "ein.tags": [
     "worksheet-0"
    ],
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "# Visualization: Activation Diagram #\n",
    "An activation diagram is a way to walk through your recursive calls, so you can visualize how we are computing the final values. Let's try to visualize `hello_recursion(10)` using an activation diagram.\n",
    "\n",
    "(Lazy Programmer here, so I'm actually writing code for it below)\n",
    "(During lecture this will get drawn out)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "autoscroll": "json-false",
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "ein.tags": [
     "worksheet-0"
    ],
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "+---------------------+\n",
      "|Hello Recursion! : 10|\n",
      "+---------------------+\n",
      "     |\n",
      "     |\n",
      "     \\/\n",
      "+--------------------+\n",
      "|Hello Recursion! : 9|\n",
      "+--------------------+\n",
      "     |\n",
      "     |\n",
      "     \\/\n",
      "+--------------------+\n",
      "|Hello Recursion! : 8|\n",
      "+--------------------+\n",
      "     |\n",
      "     |\n",
      "     \\/\n",
      "+--------------------+\n",
      "|Hello Recursion! : 7|\n",
      "+--------------------+\n",
      "     |\n",
      "     |\n",
      "     \\/\n",
      "+--------------------+\n",
      "|Hello Recursion! : 6|\n",
      "+--------------------+\n",
      "     |\n",
      "     |\n",
      "     \\/\n",
      "+--------------------+\n",
      "|Hello Recursion! : 5|\n",
      "+--------------------+\n",
      "     |\n",
      "     |\n",
      "     \\/\n",
      "+--------------------+\n",
      "|Hello Recursion! : 4|\n",
      "+--------------------+\n",
      "     |\n",
      "     |\n",
      "     \\/\n",
      "+--------------------+\n",
      "|Hello Recursion! : 3|\n",
      "+--------------------+\n",
      "     |\n",
      "     |\n",
      "     \\/\n",
      "+--------------------+\n",
      "|Hello Recursion! : 2|\n",
      "+--------------------+\n",
      "     |\n",
      "     |\n",
      "     \\/\n",
      "+--------------------+\n",
      "|Hello Recursion! : 1|\n",
      "+--------------------+\n",
      "     |\n",
      "     |\n",
      "     \\/\n",
      "+--------------------+\n",
      "|Hello Base Case! : 0|\n",
      "+--------------------+\n"
     ]
    }
   ],
   "source": [
    "def print_box(string, arrow=True):\n",
    "    print('+' + len(string)*'-' + '+')\n",
    "    print('|' + '%s' % (string) + '|')\n",
    "    print('+' + len(string)*'-' + '+')\n",
    "\n",
    "    if arrow:\n",
    "        print('     |')\n",
    "        print('     |')\n",
    "        print('     \\/')\n",
    "\n",
    "def visualize_hello_recursion(n):\n",
    "    if n <= 0:\n",
    "        print_box(\"Hello Base Case! : %d\" % (n), False)\n",
    "        return\n",
    "\n",
    "    print_box(\"Hello Recursion! : %d\" % (n))\n",
    "    return visualize_hello_recursion(n-1)\n",
    "\n",
    "visualize_hello_recursion(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Deriving a Recursive Algorithm #\n",
    "1. Assume that your algorithm solves a smaller subproblem.\n",
    "   - Name some arbiturary variable (or some arbiturary part of your algorithm) that can get smaller. You usually want to base your algorithm off of that.\n",
    "   - Come up with an english description of your algorithm. What is your function call, what parameters does it take, and how do the parameters identify your subproblems?\n",
    "2. Identify base cases\n",
    "   - What is a small problem that you already know the answer to?\n",
    "   - Is it the smallest possible problem?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "ein.tags": [
     "worksheet-0"
    ],
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "# Practical Example: Fibonnaci #\n",
    "You did fibonnacci in HW1, when we mentioned recursion was banned. The reason for it is because with recursion, you can do it in very simple code.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "autoscroll": "json-false",
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "ein.tags": [
     "worksheet-0"
    ],
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def fib(n):\n",
    "    if n < 0:\n",
    "        return 0\n",
    "\n",
    "    if n == 1:\n",
    "        return 1\n",
    "\n",
    "    return fib(n-1) + fib(n-2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "ein.tags": [
     "worksheet-0"
    ],
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "Intuitively, what recursion really does is make a smaller and smaller subproblem, until the subproblem is something we definitely know how to solve. This gives us a lot of power in terms of programming."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Fibonacci: Activation Diagram ##\n",
    "Now we are doing an operation so the activation diagram looks different. We now have something that looks like a tree!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "ein.tags": [
     "worksheet-0"
    ],
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "   \n",
    "# Example: Summing a List Recursively #\n",
    "\n",
    "## Identifying Subproblem ##\n",
    "What is a part of the algorithm that \"gets smaller\" as we sum the list?\n",
    "\n",
    "Break it down: the list gets smaller and smaller as we sum through the list (alternatively, the unsolved portion becomes smaller and smaller).\n",
    "\n",
    "So we identify our subproblem by naming an arbiturary `i`, where `i` is the current index we are solving for. That is for some arbiturary list `list`, `i` indentifies the current index `list[i..len(list)]` or `list[1..i]` both are valid solutions since **the problem is getting smaller as we solve our current step**.\n",
    "\n",
    "However, it is typically more intuitive to describe an algorithm using decreasing order, so I will use that to solve the problem.\n",
    "\n",
    "Now let's write an English Description: `sum(i)` sums a list `list` from `list[1..i]`. We can solve the sum of the entire list by calling `sum(len(list))`.\n",
    "\n",
    "## Identify the \"single step\" we need to make ##\n",
    "We need to make some decision within our subproblem. Again, we assume that a smaller problem of `sum(i-1)` gives us the solution for the smaller sublist.\n",
    "\n",
    "In this case we want to return `sum(i)`, knowing `sum(i-1)`. We can just add!\n",
    "\n",
    "\n",
    "So now we end up with the following algorithm\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "autoscroll": "json-false",
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "ein.tags": [
     "worksheet-0"
    ],
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def sum(i):\n",
    "    return list[i] + sum(i-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "ein.tags": [
     "worksheet-0"
    ],
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "However, notice that it won't compile because we are forgetting to define `list`. So let's modify our english description and move on.\n",
    "\n",
    "Our new english description:\n",
    "\n",
    "`sum(i, list)` sums a `list` from `list[0..i]`. We can solve the sum of the entire list by solving `sum(len(list), list)`.\n",
    "\n",
    "## Identify the Base Case ##\n",
    "Our algorithm is almost done: we now need to think about when our algorithm should terminate!\n",
    "\n",
    "Because of our subproblem, we should stop when `i==0`. So our final algorithm becomes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "autoscroll": "json-false",
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "ein.tags": [
     "worksheet-0"
    ],
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def sum(i, list):\n",
    "    if i == 0:\n",
    "        return 0\n",
    "\n",
    "    return list[i] + sum(i-1, list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "ein.tags": [
     "worksheet-0"
    ],
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "# Interview Questions #\n",
    "Within any of these steps, you will run into edge cases or unclear parts of the problem. In this case, ask the interviewer for clarification!\n",
    "\n",
    "1. Listen Carefully\n",
    "   - There are many details on a problem such as \"Given a sorted array...\"\n",
    "   - Your **final** solution should use all of the details in a given problem. If not, your algorithm is probably not the fastest problem\n",
    "2. Draw out an Example\n",
    "   - Draw out a physical example.\n",
    "   - Many problems have patterns and formulation that you can take advantage of\n",
    "   - Sometimes, the problem solution is well hidden in an example.\n",
    "3. Derive a Bruteforce solution\n",
    "   - Do not code yet, just state the brute force solution\n",
    "   - Typically Recursive Algorithms that might run very slow\n",
    "4. Optimize\n",
    "   - Identify redundancies.\n",
    "   - Even small `break` statements may help\n",
    "   - Would a specific data structure help?\n",
    "\t - You should always ask: Would hashmaps (dictionaries) help?\n",
    "5. Review Algorithm Before Continuing\n",
    "   - By now, you should have a good idea of what your algorithm is.\n",
    "   - Before you begin coding, take a step back: Do you have confidence in your approach?\n",
    "   - Write down what the algorithm is at a high level. Use English!\n",
    "6. Code\n",
    "   - Coding takes a long time, but make sure you code instead of focusing on your algorithm\n",
    "   - After step 5, you should be able to focus on your algorithm only.\n",
    "7. Testing\n",
    "   - Maybe you forgot an edge case. Test for a moderately large input and see what happens\n",
    "   \n",
    "Note that many people have different ideas on how to approach an actual interview. This is the most general method, and some derviation of this is what most people use to do interviews.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "ein.tags": [
     "worksheet-0"
    ],
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "# Putting it all together 1: Binary Search Algorithm #\n",
    "We will put everything together to solve the following question\n",
    "\n",
    "Given a sorted array where the elements are unique, how do we find one element in an array?\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "ein.tags": [
     "worksheet-0"
    ],
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "# Putting it all together 2: 2 Sum Problem #\n",
    "Given an array, find whether if adding two numbers in the array gives you some number `n`.\n",
    "\n",
    "\n",
    "## Nondeterminism ##\n",
    "When we make the \"choice\", sometimes we don't know what the proper choice is.\n",
    "\n",
    "Consider this subproblem: \n",
    "We are at the current step, and have already chosen `m` elements already. Obviously (since the question asks if exactly `2` elements equal a number) `m < 2`.\n",
    "\n",
    "Given that, is the current number in our answer? How do we find out?\n",
    "\n",
    "The thing is: we don't. But we do know that our problem is solved thanks to the recursion fairy. So we can \"guess\" and try all possiblities!\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.0"
  },
  "name": "6_Algorithms_Recursion.ipynb"
 },
 "nbformat": 4,
 "nbformat_minor": 2
}