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
	return total

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)
theAnswer = triangle(theNumber)
print 'Triangle=',theAnswer
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: '))

theAnswer = triangle(theNumber)
print 'Triangle=',theAnswer
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()
	answer = 0

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

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