- 《算法图解》学习笔记
divide and conquer，D&C——著名的递归式问题解决方法
D&C工作原理
1.找出简单的基线条件
2.确定如何缩小问题的规模，使其符合基线条件
（D&C是一种解决问题的思路）
举个例子
给一个数组，[1,2,3,4]，计算每个元素的相加总和
我们会想到使用循环，比如
def sum(arr):
total = 0
for i in total:
total += i
return total
print(sum([1,2,3,4]))
但是如何使用递归函数完成任务呢？
第一步：找出基线条件。最简单的数组是什么样子的呢？如果数组为空或者只有一个元素，计算就非常简单。所以这就是基线条件（编写涉及数组的递归函数时，基线条件通常是数组为空或只包含一个元素。陷入困境时，请检查基线条件是不是这样的。）
第二步：每次递归调用都要离空数组更进一步，如何缩小问题的规模呢？下面是一种方法
sum([1,2,3,4]) = 10
1 + sum([2,3,4]) = 10
计算一个数组时，计算数组第一个元素与除去第一个元素的数组的和
函数的运行过程如下：
代码如下
def arr_sum(arr):
if len(arr): # 判断数组是否为空
arr0 = arr[0]
del arr[0] # 删除第一个元素
total = arr0 + arr_sum(arr)
return total
else：
return 0
print(arr_sum([1,2,3,4]))
更简洁的
def arr_sum(arr):
if len(arr):
return arr[0] + arr_sum(arr[1:])
else:
return 0
