本文共 10599 字，大约阅读时间需要 35 分钟。
MIT 6.00.1x 第五讲-递归Recursion
** iterative algorithms-- 迭代算法
作业一
Write an iterative function iterPower(base, exp) that calculates the exponential baseexp by simply using successive multiplication. For example, iterPower(base, exp) should compute baseexp by multiplying base times itself exp times. Write such a function below.
This function should take in two values - base can be a float or an integer; exp will be an integer ≥ 0. It should return one numerical value. Your code must be iterative - use of the ** operator is not allowed.
def iterPower(base, exp): ''' base: int or float. exp: int >= 0 returns: int or float, base^exp ''' result = 1 while exp > 0: result *= base exp -= 1 return(result)
1. Recursive Algorithms
递归函数拥有两个组成部分：- recursive step：将问题不断简化成更简单的相同问题的步骤；
- base case：问题简化完成后剩下来的可以直接计算的小case
- 每一次的recursive call都会创建一个独立的环境，with local scoping of variables；当其中的一个function有返回值时，此返回值便会一层一层被带入上一层以计算出最终的结果。
2. “Classic” recursive problems
- Factorial 阶乘
def factI(n): """interative method assumes that n is an int > 0 returns n!""" res = 1 while n > 1: res = res * n n -= 1 return resdef factR(n): """recursive method assumes that n is an int > 0 returns n!""" if n == 1: return n return n*factR(n-1)
作业二
Write a function recurPower(base, exp) which computes baseexp by recursively calling itself to solve a smaller version of the same problem, and then multiplying the result by base to solve the initial problem.This function should take in two values - base can be a float or an integer; exp will be an integer ≥0. It should return one numerical value. Your code must be recursive - use of the ** operator or looping constructs is not allowed.
def recurPower(base, exp): ''' base: int or float. exp: int >= 0 returns: int or float, base^exp ''' if exp == 0: result = 1 else: result = base * recurPower(base, exp-1) return result
作业三
The function recurPower(base, exp) from Problem 2 computed baseexp by decomposing the problem into one recursive case and one base case:
baseexpbaseexp==base⋅baseexp−11ifexp>0ifexp=0
Another way to solve this problem just using multiplication (and remainder) is to note that
baseexpbaseexpbaseexp===(base2)exp2base⋅baseexp−11ifexp>0andexpisevenifexp>0andexpisoddifexp=0
Write a procedure recurPowerNew which recursively computes exponentials using this idea.
def recurPower(base, exp): ''' base: int or float. exp: int >= 0 returns: int or float, base^exp ''' if exp == 0: result = 1 elif exp % 2 == 0: result = recurPower(base*base, exp/2) else: result = base * recurPower(base, exp-1) return result
作业四
The greatest common divisor of two positive integers is the largest integer that divides each of them without remainder. For example,
gcd(2, 12) = 2gcd(6, 12) = 6gcd(9, 12) = 3gcd(17, 12) = 1
Write an iterative function, gcdIter(a, b), that implements this idea. One easy way to do this is to begin with a test value equal to the smaller of the two input arguments, and iteratively reduce this test value by 1 until you either reach a case where the test divides both a and b without remainder, or you reach 1.
def gcdIter(a, b): ''' a, b: positive integers returns: a positive integer, the greatest common divisor of a & b. ''' testvalue = min(a,b) while testvalue >= 1: if a % testvalue == 0 and b %testvalue == 0: return testvalue break testvalue -= 1 print(str(testvalue))
**3. 【补充知识-算法】Euclid’s algorithm 欧几里得算法
欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。计算公式gcd(a,b) = gcd(b,a mod b)。作业五
The greatest common divisor of two positive integers is the largest integer that divides each of them without remainder. For example,
gcd(2, 12) = 2gcd(6, 12) = 6gcd(9, 12) = 3gcd(17, 12) = 1
A clever mathematical trick (due to Euclid) makes it easy to find greatest common divisors. Suppose that a and b are two positive integers:
If b = 0, then the answer is aOtherwise, gcd(a, b) is the same as gcd(b, a % b)
Write a function gcdRecur(a, b) that implements this idea recursively. This function takes in two positive integers and returns one integer.
def gcdRecur(a, b): ''' a, b: positive integers returns: a positive integer, the greatest common divisor of a & b. ''' if b == 0: ans = a else: ans = gcdRecur(b,a%b) return ans
成功利用进阶的算法，精简了code与运算过程。
3. Towels of Hanoi
4. Fibonacci
* assert 的用法 是一种让程序检验条件是否满足的方法，若assert后面的判断为真，则程序正常向后运行；若为false，则程序自动崩溃并抛出AssertionError的异常。 5.Recursion on non-numericals
check a string of characters is a palindrome(回文), 如：Able was I ere I saw Elba.
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]) ''' 第一位与最后一位相同 and isPal(第二位一直到倒数第二位)--注意此处s[1:-1]包 括的内容 ''' return isPal(toChars(s))
其中，在此函数中，定义了两个Internal procedures，因为在外层函数的环境中，所以只有在调用isPalindrome函数时，才会连接到这两个函数。
【算法’divide and conquer’ Algorithm】
如上例子展现了divide and conquer 算法，将一个较难的问题拆分成一系列sub-problems, 它们具有如下特点： · sub-problems are easier to solve than the original · solutions of the sub-problems can be combined to solve the original【作业六】
Although Python provides a built-in function for computing the length of a string, we can write our own.Write an iterative function, lenIter, which computes the length of an input argument (a string), by counting up the number of characters in the string.
def lenIter(aStr): ''' aStr: a string returns: int, the length of aStr ''' ans = 0 for c in aStr: if c in 'abcdefghijklmnopqrstuvwxyz': ans += 1 return ans
【作业七】–未自己想出
For this problem, write a recursive function, lenRecur, which computes the length of an input argument (a string), by counting up the number of characters in the string.
Hint: String slicing may be useful in this problem…
def lenRecur(aStr): ''' aStr: a string returns: int, the length of aStr ''' if aStr == '': return 0 else: a = aStr[1:] return 1+lenRecur(a)
本题一开始并未想到，主要卡在了如何判定string只有一位的情况，但其实base case 应该是当string为空时，所以在这一点上我就错了。
【作业八】
We can use the idea of bisection search to determine if a character is in a string, so long as the string is sorted in alphabetical order.
First, test the middle character of a string against the character you’re looking for (the “test character”). If they are the same, we are done - we’ve found the character we’re looking for!
If they’re not the same, check if the test character is “smaller” than the middle character. If so, we need only consider the lower half of the string; otherwise, we only consider the upper half of the string. (Note that you can compare characters using Python’s < function.)
Implement the function isIn(char, aStr) which implements the above idea recursively to test if char is in aStr. char will be a single character and aStr will be a string that is in alphabetical order. The function should return a boolean value.
As you design the function, think very carefully about what the base cases should be.
def isIn(char, aStr): t = int(len(aStr)/2) if aStr == '': return False elif char == aStr[t]: return True elif len(aStr) == 1: return False '''原本无上面这一条elif，但因为在测试isIn('e','abc')时报错，意识到最后会陷入isIn('e','c')的无限循环，才加了如此设定 ''' elif char < aStr[t]: ans = aStr[:t] return isIn(char,ans) elif char > aStr[t]: ans = aStr[t:] return isIn(char,ans) 【修订版】
def isIn(char, aStr): t = int(len(aStr)/2) # Base case: If aStr is empty, we did not find the char. if aStr == '' : return False # Base case: See if the character in the middle of aStr equals # the test character elif char == aStr[t]: return True # Recursive case: If the test character is smaller than the middle # character, recursively search on the first half of aStr elif char < aStr[t]: ans = aStr[:t] return isIn(char,ans) # Otherwise the test character is larger than the middle character, # so recursively search on the last half of aStr elif char > aStr[t]: ans = aStr[t+1:] return isIn(char,ans)
前面一段代码之所以会出现maximum recursion depth exceeded，正是因为在char > aStr[t]的时候，我把aStr[t]这一数值仍然包含进了下一次循环中。
所以切记，如果一个数值已经确定不符合，一定要在下次循环时将其扔掉，不能再代入。 另外，养成写注释的习惯！！【作业九】
A semordnilap is a word or a phrase that spells a different word when backwards (“semordnilap” is a semordnilap of “palindromes”). Here are some examples:nametag / gatemandog / godlive / evildesserts / stressed
Write a recursive program, semordnilap, that takes in two words and says if they are semordnilap.
def semordnilapWrapper(str1, str2): # A single-length string cannot be semordnilap if len(str1) == 1 or len(str2) == 1: return False # Equal strings cannot be semordnilap if str1 == str2: return False return semordnilap(str1, str2)def semordnilap(str1, str2): ''' str1: a string str2: a string returns: True if str1 and str2 are semordnilap; False otherwise. ''' # 此种情况似乎不需要讨论 if len(str1) != len(str2): return False # 下面这段写复杂了一些，可以用一个if判断取代： # if (len(str1) == 2) & (str1[0] == str2[-1]) & (str1[-1] == str2[0]): # return True if len(str1) == 2 : if str1[0] == str2[1] and str1[1] == str2[0]: return True else: return False #下面这段可简化为： # if str1[0] == str2[-1]: # return semordnilap(str1[1:], str2[:-1]) if str1[0] == str2[-1] and semordnilap(str1[1:],str2[:-1]): return True else: return False
**三种方法在初次进入函数时做判断，而在递归中不再进行判断：
perform checks on the inputs the first time you see them, but not any subsequent time：- use keyword arguments.
- use a global variable, which you’ll see in the next lecture video; however, using global variables is always a bit risky and thus not the best way to do this.
- use a wrapper function. This wrapper function performs some checks, then makes a call to the recursive function. 作业九中即使用了此种方法。
6. global variables全局变量
作用&与function的关系：
使用global variables会在一定程度上破坏function带来的locality，并且可能会导致意想不到的结果，所以在能不用时尽量不要用。
使用全局变量的例子： 计算斐波拉契数列中函数被调用的次数 
转载地址：http://aquwi.baihongyu.com/