前一章深入介紹了遞歸交煞，本章的重點(diǎn)是使用學(xué)到的新技能來(lái)解決問(wèn)題凿蒜。我們將探索分而治之(divide and conquer速侈，D&C)—— 一種著名的遞歸式問(wèn)題解決方法抱既。
4.1 分而治之
用遞歸求一個(gè) 列表所有元素的和
def sum(list): # 重點(diǎn)是找到基線條件 遞歸條件
if list == [ ]:
return 0
return list[0] + sum(list[1:])
快速排序法，其中用到二分查找的方法：
def quicksort(array):
if len(array) < 2:
return array
else:
# 基線條件:為空或只包含一個(gè)元素的數(shù)組是“有序”的
pivot = array[0] # 遞歸條件
less = [i for i in array[1:] if i <= pivot]
greater = [i for i in array[1:] if i > pivot]
# 由所有小于基準(zhǔn)值的元素組成的子數(shù)組,
# 由所有大于基準(zhǔn)值的 元素組成的子數(shù)組
return quicksort(less) + [pivot] + quicksort(greater)
print quicksort([10, 5, 2, 3])
