递归与字典
本章节我们来学习新的概念，丰富我们的编程知识。在之前的代码中我们一直在用一种迭代的编程方式编写代码——我们创建了列表、字符串和数字区间之类的数据结构，然后编写代码迭代处理这些数据来完成计算。在本章节中，我们将从不同的角度思考这个世界，计算方法方面我们会学习一种新的计算方法：递归！数据结构方面我们也会学习一种新的叫字典的数据结构。并且，把这些概念综合在一起就能做出更复杂更有趣的作品了，当然学习也可能带来更奇怪的bug。话不多说，开始编程。
递归求和
接下来我们通过一个求和的例子来讲解递归的概念，首先让我们用之前学过的迭代的方式来解决这个问题，具体问题是这样的：我们有一个数字列表，需要计算这些数字之和。
之前的方法
# 第一种求和方法：通过列表迭代来求和
# marble:弹珠
# total：总数
# sum：求和函数
marbles = [10, 13, 39, 14, 41, 9, 3]
def compute_sum(list):
sum = 0
for number in list:
sum = sum + number
return sum
print('The total is',compute_sum(marbles))
# 第二种求和方法：使用列表内置的sum函数
print('The total is',sum(marbles))
一种不同的方法
在这种叫递归的新方法中，需要考虑两种情况。
基本情况
基本情况是你能想到的最简单的情况。那么可以求和的最简单的数字列表是什么？空列表？它的和是什么？当然是0！ compute_sum([])
递归情况
什么是递归情况呢？在递归情况中，我们要解决同一个问题的一个更小的版本。方法如下：得到雷彪中的第一项，把它加到剩余列表之和...... [10, 13, 39, 14, 41, 9, 3] = 10 + compute_sum( [13, 39, 14, 41, 9, 3])
具体代码：
# marble:弹珠
marbles = [10, 13, 39, 14, 41, 9, 3]
# recursive:递归
# compute:计算
# sum:总和
def recursive_compute_sum(list):
if len(list) == 0:
return 0
else:
first = list[0]
rest = list[1:]
sum = first + recursive_compute_sum(rest)
return sum
sum = recursive_compute_sum(marbles)
# total:总和
print('The total is', sum)
思考执行过程
利用调试功能跟进下程序的执行过程，理解一下在函数中调用自身的这种叫递归的方式。
回文检测
要理解递归这种新方法确实比较难，但这是值得我们花时间和精力的。当然我们可以仔细地把递归求和的案例分析透，不过要让我们的大脑递归地思考问题，最好的方法还是实践：提出问题，用递归的方式解决。接下来我们尝试解决一个新的问题：回文检测。
普通方法
# 方法1
# palindrome:回文
# word:单词，词语
def is_palindrome(word):
tmp = ''
for i in range(len(word)):
tmp = tmp + word[len(word)-1-i]
if(word == tmp):
return True
else:
return False
print(is_palindrome('聂岩皓'))
print(is_palindrome('聂岩皓岩聂'))
print(is_palindrome('{ }'))
# 方法2：
# palindrome:回文
# word:单词，词语
def is_palindrome(word):
i = 0
j = len(word) - 1
for i in range(int(len(word)/2)):
#while i < j:
if word[i] != word[j]:
return False
i = i + 1
j = j - 1
return True
print(is_palindrome('聂岩皓'))
print(is_palindrome('聂岩皓岩聂'))
print(is_palindrome('{ }'))
递归方法
要编写一个递归函数，首先需要一个基本情况，然后需要一种递归的情况，减小问题规模然后递归地调用同一个函数。下面就来确定基本情况和递归情况。
基本情况
基本情况就是我们能想到的最简单的情况。实际上我们可以想到两个最简单的情况。首先，考虑一下空字符串，空字符串是回文吗？它正着读和倒着读都是一样的，所以空字符串确实是回文。 is_palindrome("") 不过，还有一种很简单的情况需要考虑：单字母的情况。一个字母是回文吗？正着读和倒着读都是一样的，它也是回文。 is_palindrome("a")
递归情况
现在来看递归情况。这里才开始有些意思。要记住，让函数为我们完成任务之前，我们希望稍稍减小问题的规模。能不能这样？先比较最外面的两个字符，如果它们相同，我们再查看（稍微小一些的）单词中间部分是否是回文。 "tacocat""acoca"
回文检测器代码
def is_palindrome(word):
if len(word) <= 1:
return True
else:
if word[0] == word[-1]:
return is_palindrome(word[1:-1])
else:
return False
words = ['陈昱安积分安昱陈','a{ }a','',' ','tacocat', 'radar', 'yak', 'rader', 'kayjak']
for word in words:
print(word, is_palindrome(word))
思考执行过程
同一个函数不同次调用时内部变量的记录机制：每一次都相当于一帧，会单独记录。
斐波那契数列
递归虽然好用，但也是有一些局限性的，当然后面我们会用其他方法解决这种局限性。我们通过一个叫“斐波那契数列”的例子来展示递归中可能遇到的问题。
什么是斐波那契数列
0 1 1 2 3 5 8 ...... 前两个数字分别是0和1； 从第3个数字开始，每个数字都等于前两个数字的和。
斐波那契的递归实现
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
不同的测试结果
import time
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(20))
for i in range(20, 55, 5):
start = time.time()
result = fibonacci(i)
end = time.time()
duration = end - start
print(i, result, duration)
斐波那契测试数据
| 编号 | 答案 | 计算时间 |
|---|---|---|
| 20 | 6765 | 0.002秒 |
| 25 | 75025 | 0.04秒 |
| 30 | 832040 | 0.4秒 |
| 35 | 9227465 | 4.8秒 |
| 40 | 102334155 | 56.7秒 |
| 45 | 1134903170 | 10.5分钟 |
| 50 | 12586269025 | 1.85小时 |
看起来这个数据不太好，刚开始我们期望能在不到5秒的时间内计算出这个序列的前100个数，但从实际结果来看，单单计算第50个数就用了一个多小时！ 为什么会这样呢？可以先自己思考一下，学习了后面的知识之后我们会回过头来解决这个问题。
字典基本操作
从本节课开始，我们惠学习一种新的数据结构：字典。我们通过一个案例来讲解为什么需要字典以及如何使用字典，假设我们要做一个游戏或者APP，首先是不是需要记录一下我们的用户信息呐，比如名字、手机号、年龄等等信息。
列表的局限
要实现上面的需求，我们如果用列表的话是不是得创建好几个列表：
names = ["王小二","李大明","赵小四"]
phones = [13510909090,13094949393,19893939393]
ages = [12,10,17]
这种方法自然是可以的，但是但我们想要插入新用户的时候，是不是要往这几个列表中同时添加呢，而且要确保位置一样才可以。删除也是一样，当我们想要删除一个用户时，需要把这几个列表同时操作一下才可以。当我们想知道某个用户的信息时，则需要搜索整个列表找到他的位置，然后再从这几个列表中分别去寻找名字、手机号、年龄。而且，当我们想增加一个属性，比如性别或者邮箱的时候，该怎么办呢？是不是需要新建一个列表，然后按照上面原本姓名的顺序再一个个添加呢，这就相当复杂了。 有没有一种数据结构能够让我们为每一项指定一个好记的名字，然后把跟他相关的属性都存进去，然后寻找的时候能快速找到呢？这就是我们要讲解的字典了。
字典创建/增加/读取
创建字典
my_dictionary = {}
增加元素
字典将元素存储为键/值对，也称为key/value。假设要为我们的朋友们存储一下手机号，可以这样操作：
my_dictionary['王小二'] = 13510909090
my_dictionary['李大明'] = 13510909090
my_dictionary['赵小四'] = 19893939393
按键获取值
要想从字典获取一个值，只需要使用键：
phone_number = my_dictionary['王小二']
print('王小二的手机号是',phone_number)
字典的灵活性
对于键，可以使用数字、字符串或者布尔值。对于值，则可以使用任何合法的类型。比如
my_dictionary['age'] = 27
my_dictionary[42] = 'answer'
my_dictionary['scores'] = [92,87,99]
当然，我们也可以删除键
del my_dictionary['李大明']
不过，你可能想先测试看它是否存在。查看一个元素是否是一组对象的一部分时，比如一个列表或者字符串，Python的做法相当一致，用的是in这个关键词，字典也不例外。
if '赵李四' in my_dictionary:
print('找到他了',my_dictionary['赵李四')
else:
print("找不到他的手机号')
另外，也可以使用len()函数知道字典中有多少个键，如果已经有一个键了，再往这个键插入时，则会覆盖原来的值。
迭代字典
可以用跟列表类似的for循环来迭代字典，不过需要注意的是：字典是无序的，并不遵守插入时的先后顺序。
for key in my_dictionary:
print(key,':',my_dictionary[key])
另外，创建字典也有跟列表类似的快捷方式：
lidaming = {
'name':'李大明',
'born':1990,
'city':'河南安阳'
}
也可以将字典直接打印出来看下效果：
print(my_dictionary)
电影案例
现在我们已经掌握了字典的基本知识，接下来让我们学以致用，写一个关于电影推荐的小程序，运行之前分析一下它会输出什么内容：
movies = [] #movie:电影
movie = {}
movie['name'] = 'Forbidden Planet' #Forbidden:禁忌 Planet:星球
movie['year'] = 1957 #year:年份
movie['rating'] = '*****' #rating:评分
movie['year'] = 1956
movies.append(movie)
movie2 = {'name': 'I Was a Teenage Werewolf', #I:我 was:是的过去式 Teenage:少年 Werewolf:狼
'year': 1957, 'rating': '****'}
movie2['rating'] = '***'
movies.append(movie2)
movies.append({'name': 'Viking Women and the Sea Serpent', #维京女与海蛇
'year': 1957,
'rating': '**'})
movies.append({'name': 'Vertigo', #迷魂记
'year': 1958,
'rating': '*****'})
print('Head First Movie Recommendations') # Recommendation:推荐
print('--------------------------------')
for movie in movies:
if len(movie['rating']) >= 4:
print(movie['name'], '(' + movie['rating'] + ')', movie['year'])
这个例子中我们对单个电影用了字典来存储，多个电影用的是列表，那能不能多个电影也用电影来存储呢！当然可以，这样反而更有利于我们来理解：
movies = {}
movie = {}
movie['name'] = 'Forbidden Planet'
movie['year'] = 1957
movie['rating'] = '*****'
movie['year'] = 1956
movies['Forbidden Planet'] = movie
movie2 = {'name': 'I Was a Teenage Werewolf',
'year': 1957, 'rating': '****'}
movie2['rating'] = '***'
movies[movie2['name']] = movie2
movies['Viking Women and the Sea Serpent'] = {'name': 'Viking Women and the Sea Serpent',
'year': 1957,
'rating': '**'}
movies['Vertigo'] = {'name': 'Vertigo',
'year': 1958,
'rating': '*****'}
print('Head First Movie Recommendations')
print('--------------------------------')
for name in movies:
movie = movies[name]
if len(movie['rating']) >= 4:
print(movie['name'], '(' + movie['rating'] + ')', movie['year'])
print('Head First Movie Staff Pick')
print('---------------------------')
movie = movies['I Was a Teenage Werewolf']
print(movie['name'], '(' + movie['rating'] + ')', movie['year'])
反社交案例
现在让我们回到最初存储用户信息的例子中，学习了字典之后我们就可以用比列表更好的方式来解决这个问题了：
users = {}
users['Kim'] = {'email' : 'kim@oreilly.com','gender': 'f', 'age': 27, 'friends': ['John', 'Josh']}
users['John'] = {'email' : 'john@abc.com','gender': 'm', 'age': 24, 'friends': ['Kim', 'Josh']}
users['Josh'] = {'email' : 'josh@wickedlysmart.com','gender': 'm', 'age': 32, 'friends': ['Kim']}
基于这个数据让我们做两个有趣的计算
计算用户的平均年龄
users = {}
users['Kim'] = {'email' : 'kim@oreilly.com','gender': 'f', 'age': 27, 'friends': ['John', 'Josh']}
users['John'] = {'email' : 'john@abc.com','gender': 'm', 'age': 24, 'friends': ['Kim', 'Josh']}
users['Josh'] = {'email' : 'josh@wickedlysmart.com','gender': 'm', 'age': 32, 'friends': ['Kim']}
def average_age(username):
user = users[username]
friends = user['friends']
sum = 0
for name in friends:
friend = users[name]
sum = sum + friend['age']
average = sum/len(friends)
print(username + "'s friends have an average age of", average)
average_age('Kim')
average_age('John')
average_age('Josh')
计算最社恐的人
users = {}
users['Kim'] = {'email' : 'kim@oreilly.com','gender': 'f', 'age': 27, 'friends': ['John', 'Josh']}
users['John'] = {'email' : 'john@abc.com','gender': 'm', 'age': 24, 'friends': ['Kim', 'Josh']}
users['Josh'] = {'email' : 'josh@wickedlysmart.com','gender': 'm', 'age': 32, 'friends': ['Kim']}
max = 1000
for name in users:
user = users[name]
friends = user['friends']
if len(friends) < max:
most_anti_social = name
max = len(friends)
print('The most anti-social is', most_anti_social)
斐波那契数列优化
现在我们对字典的理解已经比较深入了，让我们回到前几集的一个遗留问题：计算斐波那契数列的时候消耗的时间太长了！看能不能用字典来优化一下。首先我们分析一下之所以计算这么慢的原因，尽管我们的代码逻辑素商事正确的，而且很清晰，但是它在计算任何一个数的斐波那契数时，这个算法都必须计算出小于这个数的所有斐波那契数。这会带来大量不必要的计算，因为我们在反复计算相同的斐波那契数。比如需要计算fibonacci(5)时，我们都必须重新计算fibonacci(4),fibonacci(3)和fibonacci(2). 那我们可以不可以记住每次计算的结果呢？这个想法相当不错，这样一来，比如说，我们之前计算过fibonacci(4)并且存储起来了，那计算fibonacci(5)的时候就可以直接使用之前存储的fibonacci(4)的结果而不需要重新计算了。也就是说我们需要保存计算n的fibonacci数的时候函数调用的结果，并且还需要在之后根据n能够快速得到之前计算的fibonacci数。是不是感觉这个逻辑有点熟悉，是的，字典请出马！
import time
cache = {}
def fibonacci(n):
global cache
if n in cache:
return cache[n]
if n == 0:
result = 0
elif n == 1:
result = 1
else:
result = fibonacci(n-1) + fibonacci(n-2)
cache[n] = result
return result
start = time.time()
for i in range(0, 101):
result = fibonacci(i)
print(i, result)
finish = time.time()
duration = finish - start
print('Computed all 100 in', duration, 'seconds')
科赫雪花
前面我们已经学习了递归以及字典的知识并且进行了多个项目的练习。本节课我们再延伸一下，递归其实不只是用来计算斐波那契数和回文，它能做的还有很多，接下来我们再来演示一个案例：用递归来生成分形图。什么是分型图呢？你可以把它想象成各种不同大小的类似的几何形状。如果你放大查看一个分形图形，会看到与放大前同样的性状。这么描述起来有点抽象，我们来实际创建一个分形图形试试看。
import turtle
def setup(pencil):
pencil.color('blue')
pencil.penup()
pencil.goto(-200,100)
pencil.pendown()
def koch(pencil, size, order):
if order == 0:
pencil.forward(size)
else:
for angle in [60, -120, 60, 0]:
koch(pencil, size/3, order-1)
pencil.left(angle)
def main():
pencil = turtle.Turtle()
setup(pencil)
turtle.tracer(100)
order = 5
size = 400
#koch(pencil, size, order)
for i in range(3):
koch(pencil, size, order)
pencil.right(120)
if __name__ == '__main__':
main()
turtle.tracer(100)
turtle.mainloop()