{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Recursion\n",
    "<a href=\"https://colab.research.google.com/github/rambasnet/FDSPython-Notebooks/blob/master/Ch13-Recursion.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>\n",
    "\n",
    "<img src=\"./resources/russiandolls.png\" width=\"50%\">\n",
    "\n",
    "- defining something in terms of itself usually at some smaller scale, perhaps multiple times, to achieve your objective\n",
    "- e.g., a human being is someone whose mother is a human being\n",
    "- directory is a structure that holds files and (smaller) directories, etc.\n",
    "- in programming, functions can generally <em>call themselves</em> to solve smaller subproblems\n",
    "- fractals is a drawing which also has self-similar structure, where it can be defined in terms of itself\n",
    "\n",
    "## Definitions\n",
    "<strong>Recursion: </strong> The process of solving a problem by reducing it to smaller versions of itself is called recursion. <br>\n",
    "<strong>Recursive definition: </strong> a definition in which something is defined in terms of smaller version of itself. <br>\n",
    "<strong>Recursive algorithm:</strong> an algorithm that finds a solution to a given problem by reducing the problem to smaller versions of itself<br>\n",
    "<strong>Infinite recursion:</strong> never stops\n",
    "\n",
    "### general construct of recurive algorithms:\n",
    "- recursive algorithms have base case(s) and general case(s)\n",
    "- base case(s) provides direct answer that makes the recursion stop\n",
    "- general case(s) recursively reduces to one of the base case(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### recursive countdown example"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Recursively print countdown from 10-1 and blast off!\n",
    "# Run it as a script\n",
    "import time\n",
    "def countDown(n):\n",
    "    if n == 0:\n",
    "        print('Blast Off!')\n",
    "        time.sleep(1)\n",
    "    else:\n",
    "        print(n)\n",
    "        time.sleep(1)\n",
    "        countDown(n-1) # tail recursion\n",
    "        #print(n)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "9\n",
      "8\n",
      "7\n",
      "6\n",
      "5\n",
      "4\n",
      "3\n",
      "2\n",
      "1\n",
      "Blast Off!\n"
     ]
    }
   ],
   "source": [
    "countDown(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fibonacci numbers\n",
    "- Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...\n",
    "- devised by Fibonacci (1170-1250), who used the sequence to model the breeding of (pairs) of rabbits\n",
    "- say in generation 7 you had 21 pairs in total, of which 13 were adults, then in next generation the adults will have bred new children, and the previous children will have grown up to become adults. So, in generation 8, you'll have 13+21=34 rabbits, of which 21 are adults."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Fibonacci number definition\n",
    "<pre>\n",
    "fib(0) = 0 - base case 1\n",
    "fib(1) = 1 - base case 2\n",
    "fib(n) = fib(n-1) + fib(n-2) for n >= 2 - general case\n",
    "</pre>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Finding Fibonacci number in series\n",
    "# count = 0\n",
    "def fib(n):\n",
    "    #global count\n",
    "    #count += 1\n",
    "    if n <= 1:\n",
    "        return n\n",
    "    f = fib(n-1) + fib(n-2)\n",
    "    return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fib(10)\n",
    "#print(count)\n",
    "#assert fib(8) == 21\n",
    "#assert fib(10) == 55"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"./resources/recursion-fib.svg\" width=\"50%\">\n",
    "\n",
    "### visualize fib(4) using pythontutor.com\n",
    "- https://goo.gl/YNizhH"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from IPython.display import IFrame\n",
    "src = \"\"\"\n",
    "http://pythontutor.com/iframe-embed.html#code=%23%20In%20Python%3A%0Adef%20fib%28n%29%3A%0A%20%20%20%20if%20n%20%3C%3D%201%3A%0A%20%20%20%20%20%20%20%20return%20n%0A%20%20%20%20f%20%3D%20fib%28n-1%29%20%2B%20fib%28n-2%29%0A%20%20%20%20return%20f%0A%20%20%20%20%0Aprint%28fib%284%29%29&codeDivHeight=400&codeDivWidth=350&cumulative=false&curInstr=0&heapPrimitives=false&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false\n",
    "\"\"\"\n",
    "IFrame(src, width=900, height=300)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### how many times is fib() called for fib(4)?\n",
    "- Modify fib to count the number of times fib gets called."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Factorial definition\n",
    "<pre>\n",
    "    0! = 1 - base case\n",
    "    n! = n.(n-1)! for n >= 1 - general case\n",
    "</pre>\n",
    "- Left as an exercise"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Drawing Fractals\n",
    "- for our purposes, a fractal is a drawing which also has self-similar structure, where it can be defined in terms of itself.\n",
    "- see Koch fractal example in text book section 18.1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### an animated fractal, using PyGame library\n",
    "- install PyGame library using the following bash script!\n",
    "- if PyGame is already installed and is the current version, there's no harm!\n",
    "- we use pip to install Python packages; so update pip just in case"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Requirement already up-to-date: pip in /Users/rbasnet/miniconda3/lib/python3.7/site-packages (19.2.1)\n",
      "Requirement already satisfied: pygame in /Users/rbasnet/miniconda3/lib/python3.7/site-packages (1.9.4)\n"
     ]
    }
   ],
   "source": [
    "%%bash\n",
    "pip install --upgrade pip\n",
    "pip install pygame"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "pygame 1.9.4\n",
      "Hello from the pygame community. https://www.pygame.org/contribute.html\n"
     ]
    }
   ],
   "source": [
    "# animated fractal; when done just close the window or force kill if not responding!\n",
    "# this program doesn't run in colab or online services. You must run locally from notebook or as a script!\n",
    "\n",
    "import pygame, math\n",
    "pygame.init()           # prepare the pygame module for use\n",
    "\n",
    "# Create a new surface and window.\n",
    "surface_size = 1024\n",
    "main_surface = pygame.display.set_mode((surface_size,surface_size))\n",
    "my_clock = pygame.time.Clock()\n",
    "\n",
    "\n",
    "def draw_tree(order, theta, sz, posn, heading, color=(0,0,0), depth=0):\n",
    "\n",
    "   trunk_ratio = 0.29       # How big is the trunk relative to whole tree?\n",
    "   trunk = sz * trunk_ratio # length of trunk\n",
    "   delta_x = trunk * math.cos(heading)\n",
    "   delta_y = trunk * math.sin(heading)\n",
    "   (u, v) = posn\n",
    "   newpos = (u + delta_x, v + delta_y)\n",
    "   pygame.draw.line(main_surface, color, posn, newpos)\n",
    "\n",
    "   if order > 0:   # Draw another layer of subtrees\n",
    "\n",
    "      # These next six lines are a simple hack to make the two major halves\n",
    "      # of the recursion different colors. Fiddle here to change colors\n",
    "      # at other depths, or when depth is even, or odd, etc.\n",
    "      if depth == 0:\n",
    "          color1 = (255, 0, 0)\n",
    "          color2 = (0, 0, 255)\n",
    "      else:\n",
    "          color1 = color\n",
    "          color2 = color\n",
    "\n",
    "      # make the recursive calls to draw the two subtrees\n",
    "      newsz = sz*(1 - trunk_ratio)\n",
    "      draw_tree(order-1, theta, newsz, newpos, heading-theta, color1, depth+1)\n",
    "      draw_tree(order-1, theta, newsz, newpos, heading+theta, color2, depth+1)\n",
    "\n",
    "\n",
    "def gameloop():\n",
    "\n",
    "    theta = 0\n",
    "    while True:\n",
    "\n",
    "        # Handle evente from keyboard, mouse, etc.\n",
    "        ev = pygame.event.poll()\n",
    "        if ev.type == pygame.QUIT:\n",
    "            break;\n",
    "\n",
    "        # Updates - change the angle\n",
    "        theta += 0.01\n",
    "\n",
    "        # Draw everything\n",
    "        main_surface.fill((255, 255, 0))\n",
    "        draw_tree(9, theta, surface_size*0.9, (surface_size//2, surface_size-50), -math.pi/2)\n",
    "\n",
    "        pygame.display.flip()\n",
    "        my_clock.tick(120)\n",
    "\n",
    "\n",
    "gameloop()\n",
    "pygame.quit()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### exercise 1\n",
    "Write a recursive fact(n) function that takes a positive integer n and returns its factorial.\n",
    "<pre>\n",
    "Here are some test cases that the fact(n) should pass:\n",
    "assert fact(5) == 120\n",
    "assert fact(10) == 3628800\n",
    "assert fact(100) == math.factorial(100)\n",
    "</pre>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### exercise 2\n",
    "Write a recursive function -- gcd(a, b) -- that finds the greatest common divisor of two given positive integers, a and b.\n",
    "- see algorithm [in Khan Academy](https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm)\n",
    "<pre>\n",
    "Here are some test cases that gcd(a, b) should pass:\n",
    "assert gcd(2, 100) == 2\n",
    "assert gcd(50, 10) == 10\n",
    "assert gcd(125, 75) == 25\n",
    "</pre>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### exercise 3\n",
    "Write a program that simulates the steps required to solve the \"Tower of Hanoii\" puzzle for some disks n.\n",
    "- https://www.mathsisfun.com/games/towerofhanoi.html\n",
    "\n",
    "- Recursive algorithm \n",
    "- If there are 1 or more disks to move:\n",
    "    1. Move the top n-1 disks from needle 1 (source) to needle 2 (helper), using needle 3 (dest) as the intermediate needle\n",
    "    2. Move disk number n from needle 1 to needle 3\n",
    "    3. Move the top n - 1 disks from needle 2 to needle 3, using needle 1 as the intermediate needle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def moveDisks(n, src, helper, dst):\n",
    "    if n > 0:\n",
    "        moveDisks(n-1, src, dst, helper)\n",
    "        print('Move disk #{} from {} to {}'.format(n, src, dst))\n",
    "        moveDisks(n-1, helper, src, dst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Move disk #1 from needle1 to needle3\n",
      "Move disk #2 from needle1 to needle2\n",
      "Move disk #1 from needle3 to needle2\n",
      "Move disk #3 from needle1 to needle3\n",
      "Move disk #1 from needle2 to needle1\n",
      "Move disk #2 from needle2 to needle3\n",
      "Move disk #1 from needle1 to needle3\n"
     ]
    }
   ],
   "source": [
    "moveDisks(3, 'needle1', 'needle2', 'needle3')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}