1.函数递归
1)问题规模大→划分小规模(如果没有问题规模,自己构建)
2)函数自己调用自己(体现问题规模不断缩小)
3)函数推出条件(防止死递归)
2斐波那契数列
public static int fibonacci(int n){
if(n==1||n==2){
return 1;
}
return fibonacci(n-1)+fibonacci(n-2);
}
public static void main(String[] args) {
int reslut=fibonacci(9);
System.out.println(reslut);
}
3二分查找
public static void main(String[]args) {
int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int result = binarySearch(9, arr,0,arr.length-1);
if(result==-1){
System.out.println("查找的数不存在");
}else{
System.out.println("存在,下标为" + result);
}
}
public static int binarySearch(int value, int arr[],int left,int right) {
while (left >> 1) + left;//left/2+right/2
if (arr[midindex] == value) {
return midindex;
}
if (arr[midindex] > value) {
return binarySearch(value,arr,left,midindex-1);
} else if (arr[midindex] < value) {
return binarySearch(value,arr,midindex+1,right);
}
}
return -1;
}