Recursion IPython Notebook

Recursion IPython Notebook

{
 "metadata": {
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Recursion\n",
      "=========\n",
      "Recursion is a technique for performing repetitive calculations.\n",
      "You should already be familiar with another way to perform repetitive, iteration.\n",
      "For and while loops are two ways to use iteration in Python.\n",
      "The characteristic that distinguishes a recursive function from an iterative solution is that the recursive function calls itself.\n",
      "That's sounds awfully confusing, why should you bother with recursion when you already know how to use iteration to do repetitive computation?\n",
      "Some problems are naturally amenable to recursive solutions, the canonical example is calculating factorials.\n",
      "\n",
      "Factorials\n",
      "----------\n",
      "Factorials show up all over the place in computer science and math.\n",
      "Example:\n",
      "$$4! = 4\\times3\\times2\\times1 = 24$$\n",
      "\n",
      "In general factorials have this form:\n",
      "$$n! = n\\times(n-1)\\times(n-2) ... \\times2\\times1$$\n",
      "The problem with that definition is the \"...\".\n",
      "A human reader knows how to interpret it but we'll need to be more precise if we want to solve factorials with a computer.\n",
      "So how can we express the factorial function unambiguously?\n",
      "\n",
      "If we take another look at the last formula we notice that there's a way to rewrite it:\n",
      "$$n! = n\\times(n-1)!$$\n",
      "\n",
      "This obviously doesn't solve our problem though, it's a circular definition.\n",
      "If we add in one more bit though we'll have a definition that works:\n",
      "$$n! = 1, n=0$$\n",
      "$$n! = n\\times(n-1)!, n>0$$\n",
      "\n",
      "So long as we use a whole number for n, this definition works.\n",
      "The first part of the definition, calld the base case, works in the simplest case.\n",
      "The second part of the definition, called the recursive case, works towards the bsae case.\n",
      "\n",
      "Let's put this into code to see how it works."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def recursive_factorial(n):\n",
      "    if n is 0:\n",
      "        return 1\n",
      "    else:\n",
      "        return n*recursive_factorial(n-1)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 15
    },
    {
     "cell_type": "code",
     "collapsed": true,
     "input": [
      "print recursive_factorial(5)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "120\n"
       ]
      }
     ],
     "prompt_number": 17
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def iterative_factorial(n):\n",
      "    result = 1\n",
      "    for i in range(1, n+1):\n",
      "        result *= i\n",
      "    return result"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print iterative_factorial(5)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "120\n"
       ]
      }
     ],
     "prompt_number": 85
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<img src=\"files/bees.jpg\">"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def fibonacci(n):\n",
      "    if n == 0:\n",
      "        return 0\n",
      "    if n == 1:\n",
      "        return 1\n",
      "    else:\n",
      "        return fibonacci(n-1) + fibonacci(n-2)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 20
    },
    {
     "cell_type": "code",
     "collapsed": true,
     "input": [
      "fibonacci(4)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 79,
       "text": [
        "3"
       ]
      }
     ],
     "prompt_number": 79
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<img src=\"files/fileTree.png\">"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def directorySize(node):\n",
      "    if node.isFile:\n",
      "        return node.fileSize\n",
      "    elif node.isDirectory:\n",
      "        #sum([directorySize(subtree) for subtree in node.children])\n",
      "        sum = 0\n",
      "        for subtree in node.children:\n",
      "            sum += directorySize(subtree)\n",
      "        return sum"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 19
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def iterative_fibonacci(n):\n",
      "    if n == 0:\n",
      "        return 0\n",
      "    if n == 1:\n",
      "        return 1\n",
      "    \n",
      "    total_so_far = 1\n",
      "    one_back = 1\n",
      "    two_back = 0\n",
      "    \n",
      "    for i in range(2,n+1):\n",
      "        total_so_far = (one_back + two_back)\n",
      "        two_back = one_back\n",
      "        one_back = total\n",
      "    \n",
      "    return total_so_far"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 37
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "iterative_fibonacci(43)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 81,
       "text": [
        "433494437"
       ]
      }
     ],
     "prompt_number": 81
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def is_palindrome(s):\n",
      "    if s =='':\n",
      "        return True\n",
      "    else:\n",
      "        if s[0] == s[-1]:\n",
      "            return is_palindrome(s[1:-1])\n",
      "        else:\n",
      "            return False"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 60
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "is_palindrome(\"racecar\")"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 84,
       "text": [
        "False"
       ]
      }
     ],
     "prompt_number": 84
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def is_palindrome_complex(s):\n",
      "    s = s.translate(None, \" ?!.,'\").lower()\n",
      "    if s =='':\n",
      "        return True\n",
      "    else:\n",
      "        if s[0] == s[-1]:\n",
      "            return is_palindrome(s[1:-1])\n",
      "        else:\n",
      "            return False"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 68
    },
    {
     "cell_type": "code",
     "collapsed": true,
     "input": [
      "is_palindrome_complex(\"Go hang a salami, I'm a lasagna hog\")"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 69,
       "text": [
        "True"
       ]
      }
     ],
     "prompt_number": 69
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}