{
"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": {}
}
]
}