递归：数组分治求和

数组分治求和

数组求和的递归是我自己瞎想的&＃xff0c;主要是想要使用归并的思想&＃xff0c;我们依然把原问题划分为子问题&＃xff0c;进而缩小问题规模。但是这里我们需要调用两次子问题&＃xff0c;我们把数组分为两个部分&＃xff0c;然后分别求解出左边数组的和&＃xff0c;右边数组的和&＃xff0c;之后将其相加就是总的和

这个问题也很好的说明了递归的一个特点&＃xff0c;那就是缩小问题规模&＃xff0c;子问题与原问题是等价的&＃xff0c;我们求解出子问题之后&＃xff0c;需要再进行一些逻辑操作。现在突然想到一个问题&＃xff0c;子问题与原问题等价吗&＃xff1f;

1. 逻辑上肯定是相同的&＃xff0c;只是问题规模缩小了。
2. 那些逻辑操作则是解决问题的

arr &＃61; [-1,2,3,4,5,6]def mergeAdd(arr, l,r):if l >&＃61; r:return arr[l]m &＃61; (l &＃43; r) // 2lsum &＃61; mergeAdd(arr, l, m)rsum &＃61; mergeAdd(arr, m&＃43;1, r)return lsum &＃43; rsumres &＃61; mergeAdd(arr,0,len(arr)-1)
print(res)


1. 终止条件&＃xff0c;当左游标大于等于右游标的时候&＃xff0c;说明只有一个元素了&＃xff0c;此时直接返回值即可
2. 子问题和重复逻辑&＃xff0c;原来求解的是0到len(arr)-1所有元素的和&＃xff0c;现在求解成子问题0到m和子问题m&＃43;1到len(arr)-1和&＃xff0c;调用了两次子问题&＃xff0c;之后将求解的和相加即是总的和