java递归的思想_递归思想-divide and conquer

递归的思想是分而治之(divide and conquer)，将一个问题域为N的问题分解(partition)成两个独立的部分，而每一个部分又是同样的问题，从而这样一直分解下去，直到问题可求为止。

如求一个数组的最大值(最小值同理)：

非递归思想解法：

public int max(int[] arr) {

int max = arr[0];

for (int i = 1, len = arr.length; i < len; ++i) {

if (arr[i] > max) {

max = arr[i];

}

}

return max;

}

递归思想：

public class MaxTest {

public int max(int[] arr) {

return recMax(arr, 0, arr.length-1);

}

private int recMax(int[] arr, int left, int right) {

if (left == right) return arr[left];

int m = (left+right)/2;

int v1 = recMax(arr, left, m);

int v2 = recMax(arr, m+1, right);

return (v1>v2)?v1:v2;

}

}