# 12: Applied Recursion¶

## Example 1: Page 238¶

In [1]:
#solves Towers of Hanoi puzzle

def doTowers(topN, src, inter, dest):
if topN == 1:	#display
print 'Disk 1 from', src, 'to', dest
else:
doTowers(topN - 1, src, dest, inter)	#src to inter

print 'Disk', topN, 'from', src, 'to', dest	#display

doTowers(topN - 1, inter, src, dest)	#inter to dest

nDisks = int(raw_input('Enter number of disks: '))	#get # of disks
doTowers(nDisks, 'A', 'B', 'C')	#solve iter

Enter number of disks: 3
Disk 1 from A to C
Disk 2 from A to B
Disk 1 from C to B
Disk 3 from A to C
Disk 1 from B to A
Disk 2 from B to C
Disk 1 from A to C


## Example 2: Page 242¶

In [2]:
#demonstrates merging two arrays into a third
from pylab import array

def merge(arrayA, sizeA, arrayB, sizeB, arrayC):	#merge A and B into C
bDex = 0
cDex = 0

while aDex < sizeA and bDex < sizeB:	#neither array empty
cDex += 1
else:
arrayC[cDex] = arrayB[bDex]
cDex += 1
bDex += 1

while aDex < sizeA:	#arrayB is empty,
arrayC[cDex] = arrayA[aDex]	#but arrayA isn't
cDex += 1

while bDex < sizeB:	#arrayA is empty,
arrayC[cDex] = arrayB[bDex]	#but arrayB isn't
cDex += 1
bDex += 1

def display(theArray, size):	#display array
print theArray

arrayA = array([23, 47, 81, 95])	#source A
arrayB = array([7, 14, 39, 55, 62, 74])	#source B
arrayC = array([None] * 10)	#destination

merge(arrayA, 4, arrayB, 6, arrayC)	#merge A+B-->C
display(arrayC, 10)	#display result
#end

[7 14 23 39 47 55 62 74 81 95]


## Example 3: Page 247¶

In [3]:
def recMergeSort(workSpace, lowerBound, upperBound):
if lowerBound == upperBound:	#if range is 1,

return	#no use sorting
else:
#find midpoint
mid = (lowerBound + upperBound) / 2
#sort low half
recMergeSort(workSpace, lowerBound, mid)
#sort high half
recMergeSort(workSpace, mid + 1, upperBound)
#merge them
merge(workSpace, lowerBound, mid + 1, upperBound)
#end else
#end recMergeSort()


## Example 4: Page 248¶

In [4]:
#demonstrates recursive merge sort
from pylab import array

class DArray:
def __init__(self, max):	#special method to create objects
#with instances customized to a specific initial state

#as private instance variables don't exist in Python,
#hence using a convention: name prefixed with an underscore, to treat them as non-public part
self._theVect = array([None] * max)	#array of Nones
self._nElems = 0	#number of data items

def _recMergeSort(self, workSpace, lowerBound, upperBound):
if lowerBound == upperBound:	#if range is 1,
return	#no use sorting
else:
#find midpoint
mid = (lowerBound + upperBound) / 2
#sort low half
self._recMergeSort(workSpace, lowerBound, mid)
#sort high half
self._recMergeSort(workSpace, mid + 1, upperBound)
#merge them
self._merge(workSpace, lowerBound, mid + 1, upperBound)
#end else
#end _recMergeSort()

def _merge(self, workSpace, lowPtr, highPtr, upperBound):
j = 0	#workspace index
lowerBound = lowPtr
mid = highPtr - 1
n = upperBound - lowerBound + 1## of items

while lowPtr <= mid and highPtr <= upperBound:
if self._theVect[lowPtr] < self._theVect[highPtr]:
workSpace[j] = self._theVect[lowPtr]
j += 1
lowPtr += 1
else:
workSpace[j] = self._theVect[highPtr]
j += 1
highPtr += 1

while lowPtr <= mid:
workSpace[j] = self._theVect[lowPtr]
j += 1
lowPtr += 1

while highPtr <= upperBound:
workSpace[j] = self._theVect[highPtr]
j += 1
highPtr += 1

for j in xrange(n):
self._theVect[lowerBound + j] = workSpace[j]
#end _merge()

def insert(self, value):	#put element into array
self._theVect[self._nElems] = value	#insert it
self._nElems += 1#increment size

def display(self):	#display array contents
for j in xrange(self._nElems):	#for each element,
print self._theVect[j],	#display it
print

def mergeSort(self):	#called by main()
#provides workspace
workSpace = array([None] * self._nElems)
self._recMergeSort(workSpace, 0, self._nElems - 1)
#end class DArray

maxSize = 100	#array size
arr = DArray(maxSize)	#create 'array'

arr.insert(64)	#insert items
arr.insert(21)
arr.insert(33)
arr.insert(70)
arr.insert(12)
arr.insert(85)
arr.insert(44)
arr.insert(3)
arr.insert(99)
arr.insert(0)
arr.insert(108)
arr.insert(36)

arr.display()	#display items
arr.mergeSort()	#merge sort the array
arr.display()	#display items again
#end

64 21 33 70 12 85 44 3 99 0 108 36
0 3 12 21 33 36 44 64 70 85 99 108