{
 "metadata": {
  "name": "",
  "signature": "sha256:de38e9569976fe6e7666e16fc87eae62ca1e6843703b45eeabd018f73553dc8b"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Chapter 6 : Recursion"
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Example 6.1  Page No : 255"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      " \n",
      "\n",
      "def triangle(n):\n",
      "    if(n==1):\n",
      "        return 1\n",
      "    else:\n",
      "        return( n + triangle(n-1) )\n",
      "\n",
      "print 'Enter a number: ' ,\n",
      "theNumber = int(raw_input())\n",
      "theAnswer = triangle(theNumber)\n",
      "print 'Triangle = ' , theAnswer\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " Enter a number: "
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "50\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " Triangle =  1275\n"
       ]
      }
     ],
     "prompt_number": 11
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Example 6.2  Page No : 265"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      " \n",
      "arrChar = []\n",
      "size = 0\n",
      "count = 0\n",
      "def doAnagram(newSize):\n",
      "    if(newSize == 1): # if too small,\n",
      "        return\n",
      "    for j in range(newSize): # for each position,\n",
      "        doAnagram(newSize-1) # anagram remaining\n",
      "        if(newSize==2): # if innermost,\n",
      "            displayWord()\n",
      "        rotate(newSize);\n",
      "\n",
      "def rotate(newSize):\n",
      "    global size\n",
      "    global arrChar\n",
      "    position = size - newSize\n",
      "    temp = arrChar[position]\n",
      "    for j in range(position+1,size):\n",
      "        # shift others left\n",
      "        arrChar[j-1] = arrChar[j]\n",
      "    arrChar[size-1] = temp;\n",
      "\n",
      "def displayWord():\n",
      "    global count\n",
      "    global size\n",
      "    global arrChar\n",
      "    if(count < 99):\n",
      "        print ' ' ,\n",
      "    if(count < 9):\n",
      "        print ' ' ,\n",
      "    count += 1\n",
      "    print count ,\n",
      "    for j in range(size):\n",
      "        print arrChar[j] ,\n",
      "    print '' ,\n",
      "    if(count%6 == 0):\n",
      "        print ''\n",
      "\n",
      "print 'Enter a word: '\n",
      "i = raw_input()\n",
      "#global size\n",
      "size = len(i)\n",
      "for j in range(size):\n",
      "    arrChar.append(i[j])\n",
      "doAnagram(size)\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter a word: \n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "cats\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "    1 c a t s      2 c a s t      3 c t s a      4 c t a s      5 c s a t      6 c s t a  \n",
        "    7 a t s c      8 a t c s      9 a s c t    10 a s t c    11 a c t s    12 a c s t  \n",
        "  13 t s c a    14 t s a c    15 t c a s    16 t c s a    17 t a s c    18 t a c s  \n",
        "  19 s c a t    20 s c t a    21 s a t c    22 s a c t    23 s t c a    24 s t a c  \n"
       ]
      }
     ],
     "prompt_number": 19
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Example 6.3  Page No : 269"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      " \n",
      "class ordArray:\n",
      "    def __init__(self,m): # constructor\n",
      "        self.a = []\n",
      "        self.nElems = 0\n",
      "    def size(self):\n",
      "        return self.nElems\n",
      "\n",
      "    def find(self,searchKey):\n",
      "        return self.recFind(searchKey, 0, self.nElems-1)\n",
      "\n",
      "    def recFind(self,searchKey,lowerBound,upperBound):\n",
      "        curIn = (lowerBound + upperBound ) / 2\n",
      "        if(self.a[curIn]==searchKey):\n",
      "            return curIn # found it\n",
      "        elif(lowerBound > upperBound):\n",
      "            return self.nElems # cant find it\n",
      "        else: # divide range\n",
      "            if(self.a[curIn] < searchKey): # its in upper half\n",
      "                return self.recFind(searchKey, curIn+1, upperBound)\n",
      "            else: # its in lower half\n",
      "                return self.recFind(searchKey, lowerBound, curIn-1)\n",
      "\n",
      "    def insert(self,value): # put element into array\n",
      "        self.a.append(value)\n",
      "        self.a.sort()\n",
      "        self.nElems += 1\n",
      "\n",
      "    def display(self): # displays array contents\n",
      "        for j in range(self.nElems): # for each element,\n",
      "            print self.a[j] , \n",
      "        print ''\n",
      "\n",
      "maxSize = 100 # array size\n",
      "arr = ordArray(maxSize) # create the array\n",
      "arr.insert(72)\n",
      "arr.insert(90)\n",
      "arr.insert(45)\n",
      "arr.insert(126)\n",
      "arr.insert(54)\n",
      "arr.insert(99)\n",
      "arr.insert(144)\n",
      "arr.insert(27)\n",
      "arr.insert(135)\n",
      "arr.insert(81)\n",
      "arr.insert(18)\n",
      "arr.insert(108)\n",
      "arr.insert(9)\n",
      "arr.insert(117)\n",
      "arr.insert(63)\n",
      "arr.insert(36)\n",
      "arr.display()  # display array\n",
      "searchKey = 27 # search for item\n",
      "if( arr.find(searchKey) != arr.size()):\n",
      "    print 'Found ' , searchKey\n",
      "else:\n",
      "    print \"Can't find \" , searchKey"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "9 18 27 36 45 54 63 72 81 90 99 108 117 126 135 144 \n",
        "Found  27\n"
       ]
      }
     ],
     "prompt_number": 13
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Example 6.4  Page No : 278"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      " \n",
      "def doTowers(topN,frm,inter,to):\n",
      "    if(topN==1):\n",
      "        print \"Disk 1 from \" , frm , \"to \" , to\n",
      "    else:\n",
      "        doTowers(topN-1, frm, to, inter) # from-->inter\n",
      "        print \"Disk \" , topN ,\" from \" , frm , \" to \" , to\n",
      "        doTowers(topN-1, inter, frm, to) # inter-->to\n",
      "\n",
      "\n",
      "nDisks = 3\n",
      "doTowers(nDisks, 'A', 'B', 'C')\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Disk 1 from  A to  C\n",
        "Disk  2  from  A  to  B\n",
        "Disk 1 from  C to  B\n",
        "Disk  3  from  A  to  C\n",
        "Disk 1 from  B to  A\n",
        "Disk  2  from  B  to  C\n",
        "Disk 1 from  A to  C\n"
       ]
      }
     ],
     "prompt_number": 14
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Example 6.5  Page no : 281"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      " \n",
      "# merge A and B into C\n",
      "def merge(arrayA,sizeA,arrayB,sizeB,arrayC ):\n",
      "    aDex=0\n",
      "    bDex=0\n",
      "    cDex=0\n",
      "    while(aDex < sizeA and bDex < sizeB):  # neither array empty\n",
      "        if( arrayA[aDex] < arrayB[bDex] ):\n",
      "            arrayC.append(arrayA[aDex])\n",
      "            cDex += 1\n",
      "            aDex += 1\n",
      "        else:\n",
      "            arrayC.append(arrayB[bDex])\n",
      "            cDex += 1\n",
      "            bDex += 1\n",
      "    while(aDex < sizeA):\n",
      "        arrayC.append(arrayA[aDex])\n",
      "        cDex += 1\n",
      "        aDex += 1\n",
      "    while(bDex < sizeB):\n",
      "        arrayC.append(arrayB[bDex]) # but arrayB isnt\n",
      "        cDex +=1\n",
      "        bDex += 1\n",
      "\n",
      "def display(theArray,size):\n",
      "    for j in range(size):\n",
      "        print theArray[j],\n",
      "\n",
      "\n",
      "\n",
      "arrayA = [23, 47, 81, 95]\n",
      "arrayB = [7, 14, 39, 55, 62, 74]\n",
      "arrayC = []\n",
      "merge(arrayA, 4, arrayB, 6, arrayC)\n",
      "display(arrayC, 10)\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "7 14 23 39 47 55 62 74 81 95\n"
       ]
      }
     ],
     "prompt_number": 15
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Example 6.6  Page no : 288"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      " \n",
      "class DArray:\n",
      "    def __init__(self,m):\n",
      "        self.theArray =  []\n",
      "        self.nElems = 0\n",
      "    \n",
      "    def insert(self,value):\n",
      "        self.theArray.append(value)\n",
      "        self.nElems += 1\n",
      "\n",
      "    def display(self):  # displays array contents\n",
      "        for j in range(self.nElems):\n",
      "           print self.theArray[j] ,\n",
      "        print ''\n",
      "\n",
      "    def mergeSort(self):\n",
      "        workSpace = []\n",
      "        for i in range(self.nElems):\n",
      "            workSpace.append(0)\n",
      "        self.recMergeSort(workSpace, 0, self.nElems-1)\n",
      "\n",
      "    def recMergeSort(self,workSpace, lowerBound,upperBound):\n",
      "        if(lowerBound == upperBound): # if range is 1,\n",
      "            return\n",
      "        else:\n",
      "            mid = (lowerBound+upperBound) / 2\n",
      "            self.recMergeSort(workSpace, lowerBound, mid)\n",
      "            self.recMergeSort(workSpace, mid+1, upperBound)\n",
      "            self.merge(workSpace, lowerBound, mid+1, upperBound)\n",
      "\n",
      "    def merge(self,workSpace,lowPtr,highPtr,upperBound):\n",
      "        j = 0\n",
      "        lowerBound = lowPtr\n",
      "        mid = highPtr-1\n",
      "        n = upperBound-lowerBound+1\n",
      "        while(lowPtr <= mid and highPtr <= upperBound):\n",
      "            if( self.theArray[lowPtr] < self.theArray[highPtr] ):\n",
      "                workSpace[j] = self.theArray[lowPtr]\n",
      "                j += 1\n",
      "                lowPtr += 1\n",
      "            else:\n",
      "                workSpace[j] = self.theArray[highPtr]\n",
      "                j += 1\n",
      "                highPtr += 1\n",
      "        while(lowPtr <= mid):\n",
      "            workSpace[j] = self.theArray[lowPtr]\n",
      "            j += 1\n",
      "            lowPtr += 1\n",
      "        while(highPtr <= upperBound):\n",
      "            workSpace[j] = self.theArray[highPtr]\n",
      "            j += 1\n",
      "            highPtr += 1\n",
      "        for j in range(n):\n",
      "            self.theArray[lowerBound+j] = workSpace[j]\n",
      "\n",
      "maxSize = 100 # array size\n",
      "arr = DArray(maxSize) # create the array\n",
      "arr.insert(64) # insert items\n",
      "arr.insert(21) \n",
      "arr.insert(33) \n",
      "arr.insert(70) \n",
      "arr.insert(12) \n",
      "arr.insert(85) \n",
      "arr.insert(44) \n",
      "arr.insert(3) \n",
      "arr.insert(99) \n",
      "arr.insert(0) \n",
      "arr.insert(108) \n",
      "arr.insert(36) \n",
      "arr.display() # display items\n",
      "arr.mergeSort() # merge sort the array\n",
      "arr.display() # display items again"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "64 21 33 70 12 85 44 3 99 0 108 36 \n",
        "0 3 12 21 33 36 44 64 70 85 99 108 \n"
       ]
      }
     ],
     "prompt_number": 16
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Example 6.7  Page No :295"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      " \n",
      "class Params: #parameters to save on stack\n",
      "    def __init__(self,nn, ra):\n",
      "        self.n=nn\n",
      "        self.returnAddress=ra\n",
      "\n",
      "class StackX:\n",
      "    def __init__(self,s):\n",
      "        self.maxSize = s\n",
      "        self.stackArray = []\n",
      "        self.top = -1\n",
      "\n",
      "    def push(self,j):\n",
      "        self.top += 1\n",
      "        self.stackArray.append(j)\n",
      "    \n",
      "    def pop(self):\n",
      "        p = self.stackArray[self.top]\n",
      "        self.top -= 1\n",
      "        self.stackArray.remove(p)\n",
      "        return p\n",
      "        \n",
      "    def peek(self):\n",
      "        return self.stackArray[self.top]\n",
      "\n",
      "    def isEmpty(self):\n",
      "        return (self.top == -1)\n",
      "\n",
      "    def isFull(self):\n",
      "        return (self.top == self.maxSize-1);\n",
      "\n",
      "theNumber = 0\n",
      "theAnswer = 0\n",
      "theStack = None\n",
      "codePart = 0\n",
      "theseParams = None\n",
      "def recTriangle():\n",
      "    global theStack,codePart\n",
      "    theStack = StackX(10000)\n",
      "    codePart = 1\n",
      "    while( step() == False): # call step() until it's true\n",
      "        pass\n",
      "\n",
      "def step():\n",
      "    global theStack,codePart,theseParams,theAnswer,theNumber\n",
      "    if codePart==1:\n",
      "        # initial call\n",
      "        theseParams = Params(theNumber, 6)\n",
      "        theStack.push(theseParams);\n",
      "        codePart = 2\n",
      "    elif codePart==2:\n",
      "        # method entry\n",
      "        theseParams = theStack.peek()\n",
      "        if(theseParams.n == 1):\n",
      "            theAnswer = 1\n",
      "            codePart = 5\n",
      "        else:\n",
      "            codePart = 3\n",
      "    elif codePart==3:\n",
      "        newParams = Params(theseParams.n - 1, 4)\n",
      "        theStack.push(newParams)\n",
      "        codePart = 2 # go enter method\n",
      "    elif codePart==4:\n",
      "        theseParams = theStack.peek()\n",
      "        theAnswer = theAnswer + theseParams.n\n",
      "        codePart = 5\n",
      "    elif codePart==5: # method exit\n",
      "        theseParams = theStack.peek()\n",
      "        codePart = theseParams.returnAddress # (4 or 6)\n",
      "        theStack.pop()\n",
      "    elif codePart==6: # return point\n",
      "        return True\n",
      "    else:\n",
      "        pass\n",
      "    return False\n",
      "\n",
      "print 'Enter a number: ' ,\n",
      "theNumber = int(raw_input())\n",
      "recTriangle()\n",
      "print 'Triangle = ' ,theAnswer\n",
      "\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter a number: "
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "100\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " Triangle =  5050\n"
       ]
      }
     ],
     "prompt_number": 17
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Example 6.8  Page no : 301"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      " \n",
      "\n",
      "\n",
      "class StackX:\n",
      "    def __init__(self,s):\n",
      "        self.maxSize = s\n",
      "        self.stackArray = []\n",
      "        self.top = -1\n",
      "\n",
      "    def push(self,j):\n",
      "        self.top += 1\n",
      "        self.stackArray.append(j)\n",
      "    \n",
      "    def pop(self):\n",
      "        p = self.stackArray[self.top]\n",
      "        self.top -= 1\n",
      "        self.stackArray.remove(p)\n",
      "        return p\n",
      "        \n",
      "    def peek(self):\n",
      "        return self.stackArray[self.top]\n",
      "\n",
      "    def isEmpty(self):\n",
      "        return (self.top == -1)\n",
      "\n",
      "    def isFull(self):\n",
      "        return (self.top == self.maxSize-1);\n",
      "theNumber = 0\n",
      "theAnswer = 0\n",
      "theStack = None\n",
      "theseParams = None\n",
      "\n",
      "def stackTriangle():\n",
      "    global theNumber,theAnswer,theStack,theNumber\n",
      "    theStack = StackX(10000)\n",
      "    theAnswer = 0\n",
      "    while(theNumber > 0): # until n is 1,\n",
      "        theStack.push(theNumber) # push value\n",
      "        theNumber -= 1 # decrement value\n",
      "\n",
      "    while( not theStack.isEmpty() ): # until stack empty,\n",
      "        newN = theStack.pop() # pop value,\n",
      "        theAnswer += newN\n",
      "\n",
      "print 'Enter a number: ' ,\n",
      "theNumber = int(raw_input())\n",
      "stackTriangle()\n",
      "print 'Triangle = ' ,theAnswer\n",
      "\n",
      "\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter a number: "
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "50\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " Triangle =  1275\n"
       ]
      }
     ],
     "prompt_number": 18
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}