# Chapter 6 : Recursion¶

### Example 6.1 Page No : 255¶

In [11]:


def triangle(n):
if(n==1):
return 1
else:
return( n + triangle(n-1) )

print 'Enter a number: ' ,
theNumber = int(raw_input())
print 'Triangle = ' , theAnswer

 Enter a number: 50
Triangle =  1275


### Example 6.2 Page No : 265¶

In [19]:

arrChar = []
size = 0
count = 0
def doAnagram(newSize):
if(newSize == 1): # if too small,
return
for j in range(newSize): # for each position,
doAnagram(newSize-1) # anagram remaining
if(newSize==2): # if innermost,
displayWord()
rotate(newSize);

def rotate(newSize):
global size
global arrChar
position = size - newSize
temp = arrChar[position]
for j in range(position+1,size):
# shift others left
arrChar[j-1] = arrChar[j]
arrChar[size-1] = temp;

def displayWord():
global count
global size
global arrChar
if(count < 99):
print ' ' ,
if(count < 9):
print ' ' ,
count += 1
print count ,
for j in range(size):
print arrChar[j] ,
print '' ,
if(count%6 == 0):
print ''

print 'Enter a word: '
i = raw_input()
#global size
size = len(i)
for j in range(size):
arrChar.append(i[j])
doAnagram(size)

Enter a word:
cats
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
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
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
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


### Example 6.3 Page No : 269¶

In [13]:

class ordArray:
def __init__(self,m): # constructor
self.a = []
self.nElems = 0
def size(self):
return self.nElems

def find(self,searchKey):
return self.recFind(searchKey, 0, self.nElems-1)

def recFind(self,searchKey,lowerBound,upperBound):
curIn = (lowerBound + upperBound ) / 2
if(self.a[curIn]==searchKey):
return curIn # found it
elif(lowerBound > upperBound):
return self.nElems # cant find it
else: # divide range
if(self.a[curIn] < searchKey): # its in upper half
return self.recFind(searchKey, curIn+1, upperBound)
else: # its in lower half
return self.recFind(searchKey, lowerBound, curIn-1)

def insert(self,value): # put element into array
self.a.append(value)
self.a.sort()
self.nElems += 1

def display(self): # displays array contents
for j in range(self.nElems): # for each element,
print self.a[j] ,
print ''

maxSize = 100 # array size
arr = ordArray(maxSize) # create the array
arr.insert(72)
arr.insert(90)
arr.insert(45)
arr.insert(126)
arr.insert(54)
arr.insert(99)
arr.insert(144)
arr.insert(27)
arr.insert(135)
arr.insert(81)
arr.insert(18)
arr.insert(108)
arr.insert(9)
arr.insert(117)
arr.insert(63)
arr.insert(36)
arr.display()  # display array
searchKey = 27 # search for item
if( arr.find(searchKey) != arr.size()):
print 'Found ' , searchKey
else:
print "Can't find " , searchKey

9 18 27 36 45 54 63 72 81 90 99 108 117 126 135 144
Found  27


### Example 6.4 Page No : 278¶

In [14]:

def doTowers(topN,frm,inter,to):
if(topN==1):
print "Disk 1 from " , frm , "to " , to
else:
doTowers(topN-1, frm, to, inter) # from-->inter
print "Disk " , topN ," from " , frm , " to " , to
doTowers(topN-1, inter, frm, to) # inter-->to

nDisks = 3
doTowers(nDisks, 'A', 'B', 'C')

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 6.5 Page no : 281¶

In [15]:

# merge A and B into C
def merge(arrayA,sizeA,arrayB,sizeB,arrayC ):
bDex=0
cDex=0
while(aDex < sizeA and bDex < sizeB):  # neither array empty
cDex += 1
else:
arrayC.append(arrayB[bDex])
cDex += 1
bDex += 1
cDex += 1
while(bDex < sizeB):
arrayC.append(arrayB[bDex]) # but arrayB isnt
cDex +=1
bDex += 1

def display(theArray,size):
for j in range(size):
print theArray[j],

arrayA = [23, 47, 81, 95]
arrayB = [7, 14, 39, 55, 62, 74]
arrayC = []
merge(arrayA, 4, arrayB, 6, arrayC)
display(arrayC, 10)

7 14 23 39 47 55 62 74 81 95


### Example 6.6 Page no : 288¶

In [16]:

class DArray:
def __init__(self,m):
self.theArray =  []
self.nElems = 0

def insert(self,value):
self.theArray.append(value)
self.nElems += 1

def display(self):  # displays array contents
for j in range(self.nElems):
print self.theArray[j] ,
print ''

def mergeSort(self):
workSpace = []
for i in range(self.nElems):
workSpace.append(0)
self.recMergeSort(workSpace, 0, self.nElems-1)

def recMergeSort(self,workSpace, lowerBound,upperBound):
if(lowerBound == upperBound): # if range is 1,
return
else:
mid = (lowerBound+upperBound) / 2
self.recMergeSort(workSpace, lowerBound, mid)
self.recMergeSort(workSpace, mid+1, upperBound)
self.merge(workSpace, lowerBound, mid+1, upperBound)

def merge(self,workSpace,lowPtr,highPtr,upperBound):
j = 0
lowerBound = lowPtr
mid = highPtr-1
n = upperBound-lowerBound+1
while(lowPtr <= mid and highPtr <= upperBound):
if( self.theArray[lowPtr] < self.theArray[highPtr] ):
workSpace[j] = self.theArray[lowPtr]
j += 1
lowPtr += 1
else:
workSpace[j] = self.theArray[highPtr]
j += 1
highPtr += 1
while(lowPtr <= mid):
workSpace[j] = self.theArray[lowPtr]
j += 1
lowPtr += 1
while(highPtr <= upperBound):
workSpace[j] = self.theArray[highPtr]
j += 1
highPtr += 1
for j in range(n):
self.theArray[lowerBound+j] = workSpace[j]

maxSize = 100 # array size
arr = DArray(maxSize) # create the 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

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


### Example 6.7 Page No :295¶

In [17]:

class Params: #parameters to save on stack
def __init__(self,nn, ra):
self.n=nn

class StackX:
def __init__(self,s):
self.maxSize = s
self.stackArray = []
self.top = -1

def push(self,j):
self.top += 1
self.stackArray.append(j)

def pop(self):
p = self.stackArray[self.top]
self.top -= 1
self.stackArray.remove(p)
return p

def peek(self):
return self.stackArray[self.top]

def isEmpty(self):
return (self.top == -1)

def isFull(self):
return (self.top == self.maxSize-1);

theNumber = 0
theStack = None
codePart = 0
theseParams = None
def recTriangle():
global theStack,codePart
theStack = StackX(10000)
codePart = 1
while( step() == False): # call step() until it's true
pass

def step():
if codePart==1:
# initial call
theseParams = Params(theNumber, 6)
theStack.push(theseParams);
codePart = 2
elif codePart==2:
# method entry
theseParams = theStack.peek()
if(theseParams.n == 1):
codePart = 5
else:
codePart = 3
elif codePart==3:
newParams = Params(theseParams.n - 1, 4)
theStack.push(newParams)
codePart = 2 # go enter method
elif codePart==4:
theseParams = theStack.peek()
codePart = 5
elif codePart==5: # method exit
theseParams = theStack.peek()
codePart = theseParams.returnAddress # (4 or 6)
theStack.pop()
elif codePart==6: # return point
return True
else:
pass
return False

print 'Enter a number: ' ,
theNumber = int(raw_input())
recTriangle()

Enter a number: 100
Triangle =  5050


### Example 6.8 Page no : 301¶

In [18]:


class StackX:
def __init__(self,s):
self.maxSize = s
self.stackArray = []
self.top = -1

def push(self,j):
self.top += 1
self.stackArray.append(j)

def pop(self):
p = self.stackArray[self.top]
self.top -= 1
self.stackArray.remove(p)
return p

def peek(self):
return self.stackArray[self.top]

def isEmpty(self):
return (self.top == -1)

def isFull(self):
return (self.top == self.maxSize-1);
theNumber = 0
theStack = None
theseParams = None

def stackTriangle():
theStack = StackX(10000)
while(theNumber > 0): # until n is 1,
theStack.push(theNumber) # push value
theNumber -= 1 # decrement value

while( not theStack.isEmpty() ): # until stack empty,
newN = theStack.pop() # pop value,

Enter a number: 50