分而治之(D&C)一种著名的递归式问题的解决方法。
案例:农场主分地问题:
要求:要将这块地均匀分成方块,且分出的方块尽可能大。
步骤:(1)找出基线条件,这种条件必须尽可能的简单
(2)不断将问题分解(或者说是缩小规模),直到符合基线条件
这个案例很有意思,而且后面的顿悟时刻:为何不对余下的那一块小块地使用相同的算法呢?这正是递归的核心思想啊。
另一个小例子:
给定一个数组:2,4,6
需要将这些数字相加,并返回结果。使用循环很容易。
1 | public static int sum(int[] arr){ |
如何用递归完成这种任务呢?
第一步:找出基线条件。最简单的数组:不包含任何元素或只包含元素,这样计算总和非常容易。
第二步:每次递归调用都必须离空数组更进一步。
那么如何缩小问题的规模呢?给sum传递的数组更短。
练习:
4.1:实现前述sum函数
分析:这个问题基线条件比较清晰,不太清晰的点其实是递归条件,如何让数组离空数组更近一步呢?一开始我想的是,把数组截取,让数组长度每次调用都减一。其实这样想就有点偏差了,因为让数组变成空数组,其实并不是真的让数组逐渐的变为空数组,其实一直都是原来的数组,只不过每次调用的元素都是数组中的不同元素。下面的代码可能会更加帮助理解递归条件:
代码如下:
1 | /* |
4.2:编写一个递归函数来计算列表包含的元素数
分析:乍一看这个问题和4.1不太一样,但是如果数组中每个元素的值都是1的话,是不是这时候求数组的和,得到的就是列表中所包含的元素数。所以只需要把上述的代码稍做修改即可。
代码如下:
1 | /* |
4.3:找出列表中最大的数字
分析:这个问题就比前两个深化一些了,要找出列表中的最大值,其实有很多方法。如果用递归去做,其实还是要考虑基线条件和递归条件。和前两个问题类似,递归条件还是想让传入的数组的长度原来越短,换句话说就是,想要比较的元素数越来越少。这里可以把一个数组分割成为两个,通过数组的下标做判断。左数组找出一个最大值,右数组找一个最大值,再进行比较,返回大的那个。
代码如下:
1 | public static int findMax(int[] arr,int leftIndex,int rightIndex){ |
我的测试数组为2,4,6,8