Lecture 5 - Recursion
1. ITERATIVE ALGORITHMS
concept: Looping constructs (e.g. while or for loops) lead naturally to iterative algorithms
def iterMul(a, b):
result = 0
while b > 0:
result += a
b -= 1
return result
2. Recursion
Reduce a PRoblem to a simpler (or smaller) version of
the same problem, plus some simple computations
Recursive step
– Keep reducing un0l reach a simple case that can be
solved directly
Base case
def recurMul(a, b):
if b == 1:
return a
else:
return a + recurMul(a, b-1)
3. TOWERS OF HANOI
1 count = 1
2
3 def test(num, src, dst, rest):
4 global count
5
6 if num < 1:
7 print False
8 elif num == 1:
9 print "%d:\t%s -> %s" % (count, src, dst)
10 count += 1
11 elif num > 1:
12 test(num - 1, src, rest, dst)
13 test(1, src, dst, rest)
14 test(num - 1, rest, dst, src)
15
16
17 test(3, 'A', 'C', 'B')
4. FIBONACCI
def fib(x):
"""assumes x an int >= 0
returns Fibonacci of x"""
assert type(x) == int and x >= 0
if x == 0 or x == 1:
return 1
else:
return fib(x-1) + fib(x-2)
5. isPal
def isPalindrome(s):
def toChars(s):
s = s.lower()
ans = ''
for c in s:
if c in 'abcdefghijklmnopqrstuvwxyz':
ans = ans + c
return ans
def isPal(s):
if len(s) <= 1:
return True
else:
return s[0] == s[-1] and isPal(s[1:-1])
return isPal(toChars(s))
5. GLOBAL VARIABLES
def fibMetered(x):
global numCalls
numCalls += 1
if x == 0 or x == 1:
return 1
else:
return fibMetered(x-1) + fibMetered(x-2)
def testFib(n):
for i in range(n+1):
global numCalls
numCalls = 0
print('fib of ' + str(i) + ' = ' + str(fibMetered(i)))
print('fib called ' + str(numCalls) + ' times')
