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())
theAnswer = triangle(theNumber)
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 ):
    aDex=0
    bDex=0
    cDex=0
    while(aDex < sizeA and bDex < sizeB):  # neither array empty
        if( arrayA[aDex] < arrayB[bDex] ):
            arrayC.append(arrayA[aDex])
            cDex += 1
            aDex += 1
        else:
            arrayC.append(arrayB[bDex])
            cDex += 1
            bDex += 1
    while(aDex < sizeA):
        arrayC.append(arrayA[aDex])
        cDex += 1
        aDex += 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
        self.returnAddress=ra

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
theAnswer = 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():
    global theStack,codePart,theseParams,theAnswer,theNumber
    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):
            theAnswer = 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()
        theAnswer = theAnswer + theseParams.n
        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()
print 'Triangle = ' ,theAnswer

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
theAnswer = 0
theStack = None
theseParams = None

def stackTriangle():
    global theNumber,theAnswer,theStack,theNumber
    theStack = StackX(10000)
    theAnswer = 0
    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,
        theAnswer += newN

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

Enter a number: 50
 Triangle =  1275
In [ ]: