本文共 2654 字，大约阅读时间需要 8 分钟。

3.递归

编写递归函数时，必须告诉它何时停止递归。正因为如此，每个递归函数都有两部分：基线条件（base case）和递归条件（recursive case）。递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己，从而避免形成无限循环。

def countdown(i):    print(i)    if i <= 0:   #基线条件        return    else:       #递归条件        countdown(i - 1)print(countdown(6))

运行结果：

6 5 4 3 2 1 0

小结：

1. 递归指的是调用自己的函数
2. 每个递归函数都有两个条件：基线条件和递归条件
3. 栈有两种操作：压入和弹出
4. 所有函数调用都进入调用栈
5. 调用栈可能很长，这将占用大量的内存
   4.快速排序
   4.1分而治之
   快速排序使用分而治之的策略（divide and conquer,D&C）——一种著名的递归式问题解决方法。
   使用D&C解决问题的过程包括两个步骤：
   （1）找出基准条件，这种条件必须尽可能简单
   （2）不断将问题分解（或者是缩小规模），直到符合基线条件
   4.2快速排序步骤
   （1）选择基准值
   （2）将列表分成两个子列表：小于基准值的元素和大于基准值的元素
   （3）对这两个子列表进行快速排序
   快速排序的代码实现:

def quicksort(my_list):    if len(my_list) < 2:        return my_list     #基线条件：为空或只包含一个元素的列表是“有序”的    else:        pivot = my_list[0]  #递归条件        less = [i for i in my_list[1:] if i <= pivot] #由所有小于基准值的元素组成的子列表        greater = [i for i in my_list[1:] if i > pivot] #由所有大于基准值的元素组成的子列表        return quicksort(less) + [pivot] + quicksort(greater)print(quicksort([9,3,8,2,6]))

运行结果：

[2, 3, 6, 8, 9]

4.4小结

• D&C将问题逐步分解。使用D&C处理列表时，基线条件很可能是空列表或只包含一个元素的列表
• 实现快速排序时，请随机选择用作基准值的元素。快速排序的平均运行时间为O(nlogn)，其中层数为O(logn)，用技术术语说，调用栈的高度为O(logn)，而每层需要的时间为O(n)
• 大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在
• 比较简单查找和二分查找时，常量几乎无关紧要，因为列表很长时，O(logn)的速度比O(n)快得多
  5.散列表
  5.2.2防止重复

voted = {}def check_voter(name):    if voted.get(name):        print('kick them out!')    else:        voted[name] = True        print('let them vote!')

运行结果：

check_voter(‘Tom’) let them vote! check_voter(‘Jerry’) let them vote! check_voter(‘Jerry’) kick them out! 首先来投票的是Tom，上述代码打印let them vote!。接着Jerry来投票，打印的也是let them vote!。然后，Jerry又来投票，于是打印的就是kick them out！。 5.2.4小结 散列表适用于：

• 模拟映射关系
• 防止重复
• 缓存/记住数据，以免服务器再通过处理来生成它们
  6.广度优先搜索

#广度优先搜索#定义有向图graph = {}graph['you'] = ['alice','bob','claire']graph['bob'] = ['anuj','peggy']graph['alice'] = ['peggy']graph['claire'] = ['thom','jonny']graph['anuj'] = []graph['peggy'] = []graph['thom'] = []graph['jonny'] = []def person_is_seller(name):    return name[-1] == 'm'  #假定姓名以m结尾的就是芒果销售商from collections import dequedef search(name):    search_queue = deque()     #创建一个队列    search_queue += graph[name]  #将你的邻居都加入到这个搜索队列中    searched = []          #这个列表用于记录检查过的人    while search_queue:   #只要队列不为空        person = search_queue.popleft()  #就取出其中的第一个人        if not person in searched:   #仅当这个人没检查过时才检查            if person_is_seller(person): #检查这个人是否是芒果销售商                print(person+' is a mango seller!')  #是芒果销售商                return True            else:                search_queue += graph[person] #不是芒果销售商，将这个人的朋友都加入搜索队列                searched.append(person)  #将这个人标记为检查过    return False  #如果到达了这里，就说明队列中没人是芒果销售商search('you')

运行结果：

thom is a mango seller! 广度优先搜索的运行时间为O(V+E),其中V为顶点，E为边数。

转载地址：http://mncii.baihongyu.com/