递归，分治是一种常见迭代方法。在二叉树遍历，线性表中遍历十分常见。
递归、分治最核心的思想是 递推。 从外层–》内层，压栈，使得计算规模不断减小。 从内层–》外层，出栈，需要把计算结果传递给外层，做计算。
编写代码请问下自己下面几个问题： 1、传入的参数是什么，是作为缓冲来接收吗， 2.、返回的结果是什么，这个结果需要带入到外层递推公式中。 3、外层函数主要包括： 递归的终结点，和计算过程。 写在递归式的前面 4、内层函数不断返回值，写在递归式的后面 5、你需要把结果带入到函数中，可以一句话概括一个函数的作用
package myLeetcode.divide_conquer; /** * 方法一： * 递推式： * 参数： left,right; * 思路：当前层最大值=max（max左，max右） * 外层函数:（入栈） * 1、分的终点：最后两个结点，返回其最大值 * 2、分的函数体，mid=(left + right )/2 ,并分别求其左右两边最小值 * 3、递推式：[left:,mid] 和[mid+1,right] * * 内层函数： * 出栈：把左右两边的结果求最大值 方法二： 递推是 max=max(method(m-1),array[m]); 终结点是： 当m=1, 出栈，返回当前函数的结果即可 方法三： 传入的参数当前的max，如果当前值array[m]比原来的max更大就更新 终结点:m到达0 出栈：返回方法结果，【终点掌握，传参来接收最大值，用以此来返回】 * */ public class MaxTestInD_C { public static void main(String[] args) { int[] array={2,6,5,55,3,0,99,8,9,-1,1}; System.out.println(max(array,0,array.length-1)); System.out.println(max2(array,array.length-1)); System.out.println(max3(array,array.length-1,array[array.length-1])); } //分治法求数组最大值;返回的是两个索引的最大值 public static int max(int[] array, int left, int right) { if (left + 1 >= right) { return Math.max(array[left], array[right]); } int mid = (left + right) / 2; int leftMax = max(array, left, mid); int rightMax = max(array, mid + 1, right); return Math.max(leftMax, rightMax); } //递归法，只需要处理最后的一步就好了：缺点需要多次调用max public static int max2(int[] array,int m){ if (m ==1){ int maxFinal= Math.max(array[0],array[1]); return maxFinal; } int maxFinal=Math.max(max2(array,m-1),array[m]); return maxFinal; } //分治： //用maxNum2来保存最大的值，如果有更大的就更新， // 每次返回的是array[maxIndex] > maxNum2 public static int max3(int[] array ,int maxIndex,int maxNum2){ if ( maxIndex == 0){ return maxNum2; } if (array[maxIndex] > maxNum2){ maxNum2 =array[maxIndex]; } int maxFinal= max3(array,maxIndex-1,maxNum2); return maxFinal;//出栈时候要返回的是结果 } }