Lecture 5 - Recursion

2019-11-06 06:38:34

字體：大中小

來源：轉載

供稿：網友

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 += 111 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')

上一篇：spring使用context:property-placeholder載不進屬性問題

下一篇：【Leetcode】401. Binary Watch