# 11: Recursion¶

## Example 1: Page 209¶

In [1]:
def triangle(n):
total = 0
while n > 0:	#until n is 1
total = total + n	#add n (column height) to total
n -= 1	#decrement column height


## Example 2: Page 211¶

In [2]:
def triangle(n):
if n == 1:
return 1
else:
return n + triangle(n-1)


## Example 3: Page 212¶

In [3]:
#evaluates triangular numbers
from sys import setrecursionlimit

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

theNumber = int(raw_input('Enter a number: '))
setrecursionlimit(1030)

Enter a number: 1000
Triangle= 500500


## Example 4: Page 213¶

In [4]:
#evaluates triangular numbers

def triangle(n):
print 'Entering: n=', n
if n == 1:
print 'Returning 1'
return 1
else:
temp = n + triangle(n-1)
print 'Returning', temp
return temp

theNumber = int(raw_input('Enter a number: '))


Enter a number: 5
Entering: n= 5
Entering: n= 4
Entering: n= 3
Entering: n= 2
Entering: n= 1
Returning 1
Returning 3
Returning 6
Returning 10
Returning 15
Triangle= 15


## Example 5: Page 220¶

In [5]:
def anagram(newSize):
if newSize == 1:
return

for j in xrange(newSize):
anagram(newSize - 1)
if newSize == 2:
displayWord()
rotate(newSize)


## Example 6: Page 221¶

In [6]:
#creates anagrams

class word:
def __init__(self, inpStr):	#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._size = len(inpStr)	#length of input word (number of characters)
self._count = 0	#numbers in display
self._workStr = inpStr	#workspace (initialize workStr)

def anagram(self, newSize):	#anagram ourselves
if newSize == 1:	#if too small
return	#go no further

for j in xrange(newSize):	#for each position,
self.anagram(newSize - 1)	#anagram remaining
if newSize == 2:	#if innermost,
self._displayWord()	#	display it
self._rotate(newSize)	#rotate word

#rotate left all chars from position to end
def _rotate(self, newSize):	#rotate part of workStr
position = self._size - newSize
#logic changed here as, Python strings are immutable
str2 = self._workStr[position + 1 :] + self._workStr[position]	#shifted substring from position till end

str1 = self._workStr[: position]	#substring from start till position(position non included)

self._workStr = str1 + str2	#complete shifted string

def _displayWord(self):	#display workStr
if self._count < 99:	#spaces before one-
print '',			#or two-digit numbers
if self._count < 9:
print '',
self._count += 1
print self._count, self._workStr,	#number
if not self._count%6:
print

Input = raw_input('Enter a word: ')	#get word
length = len(Input)	#get its length

theWord = word(Input)	#make a word object
theWord.anagram(length)	#anagram it
#end

Enter a word: cats
1 cats   2 cast   3 ctsa   4 ctas   5 csat   6 csta
7 atsc   8 atcs   9 asct  10 astc  11 acts  12 acst
13 tsca  14 tsac  15 tcas  16 tcsa  17 tasc  18 tacs
19 scat  20 scta  21 satc  22 sact  23 stca  24 stac


## Example 7: Page 223¶

In [7]:
def find(searchKey):
lowerBound = 0
upperBound = nElems - 1

while(True):
curIn = (lowerBound + upperBound) / 2
if v[curIn] == searchKey:
return curIn	#found it
elif lowerBound > upperBound:
return nElems	#can't find it
else:	#divide range
if v[curIn] < searchKey:
lowerBound = curIn + 1	#it's in upper half
else:
upperBound = curIn - 1	#it's in lower half
#end else divide range
#end while
#end find()


## Example 8: Page 223¶

In [8]:
def recFind(searchKey, lowerBound, upperBound):

curIn = (lowerBound + upperBound) / 2

if v[curIn] == searchKey:
return curIn	#found it
elif lowerBound > upperBound:
return nElems	#can't find it
else:	#divide range
if v[curIn] < searchKey:	#it's in upper half
recFind(searchKey, curIn + 1, upperBound)
else:	#it's in lower half
recFind(searchKey, lowerBound, curIn - 1)
#end else divide range
#end recFind()


## Example 9: Page 224¶

In [9]:
def find(searchKey):
return recFind(searchKey, 0, nElems-1)


## Example 10: Page 224¶

In [10]:
#demonstrates recursive binary search

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

#since 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._v = []	#list _v

def getSize(self):	#return # of elements
return len(self._v)

def find(self, searchKey):	#initial find()
return self.recFind(searchKey, 0, len(self._v)-1)

#recursive find()
def recFind(self, searchKey, lowerBound, upperBound):

curIn = (lowerBound + upperBound) / 2

if self._v[curIn] == searchKey:
return curIn	#found it
elif lowerBound > upperBound:
return nElems	#can't find it
else:	#divide range
if self._v[curIn] < searchKey:	#it's in upper half
self.recFind(searchKey, curIn + 1, upperBound)
else:	#it's in lower half
self.recFind(searchKey, lowerBound, curIn - 1)
#end else divide range
#end recFind()

def insert(self, value):	#put element into array
j = 0
for j, val in enumerate(self._v):	#find where it goes
if val > value:	#(linear search)
break
else:
j += 1

self._v.insert(j, value)	#insert it

def display(self):	#display array contents
print self._v	#display it
#end class OrdArray

arr = OrdArray()	#ordered array

arr.insert(72)	#insert items
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.getSize():
print 'Found', searchKey
else:
print "Can't Find", searchKey
#end

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


## Example 11: Page 229¶

In [2]:
#evaluates triangular numbers, stack replaces recursion

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

#since 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._stackVect = []	#list used as stack

def push(self, j):	#put item on top of stack
self._stackVect.append(j)

def pop(self):	#take item from top of stack
return self._stackVect.pop()

def peek(self):	#peek at top of stack
return self._stackVect[-1]

def isEmpty(self):	#true if stack is empty
return not self._stackVect
#end class StackX

def stackTriangle(number):
theStack = StackX()

while number > 0:
theStack.push(number)
number -= 1
while not theStack.isEmpty():
newN = theStack.pop()

theNumber = int(raw_input('Enter a number: '))
#end

Enter a number: 5
Triangle= 15