1，递归的概念

一个方法在执行过程中调用自己，就称为递归

要写出递归的代码需要两个条件

1. 终止条件
2. 递归公式

例子1：递归求N的阶乘

public static int fac(int n) {
        if(n == 1) {
            return 1;
        }
        return n * fac(n-1);
}

当n = 3时

关于调用栈

方法调用的时候，会有一个“栈”这样的内存空间描述调用关系，称为调用栈

每⼀次的⽅法调⽤就称为⼀个"栈帧",每个栈帧中包含了这次调⽤的参数是哪些,返回到哪⾥继续执 ⾏等信息.

例子2：按顺序打印⼀个数字的每⼀位(例如1234打印出1234)

public static void printNum(int n) {
        if(n < 10) {
            System.out.print(n+" ");
        }else {
            printNum(n / 10);
            System.out.print(n % 10+" ");
        }
}

例子3：递归求1+2+3+...+10

public static int facAdd(int n) {
        if(n == 1) {
            return 1;
        }
        return n + facAdd(n - 1);
}

例子4：写⼀个递归⽅法，输⼊⼀个⾮负整数，返回组成它的数字之和.例如，输⼊1729,则应该返 回1+7+2+9，它的和是19

public static int sum(int n) {
        if(n < 10) {
            return n;
        }
        return n % 10 +sum(n / 10);
}

例子5：求斐波那契数列的第N项

public static int fib(int n) {
        if(n == 1 || n == 2) {
            return 1;
        }
        return fib(n - 1) + fib(n - 2);
}

2，数组的定义和使用

2.1 什么是数组？

数组是一类数据的集合

• 数组是连续存放的
• 数组有编号从0开始的

2.2 数组的创建即初始化

T [] 数组名 = new T[N]

T表示数组中存放数据的类型

T []是数组的类型

N表示数组中元素的个数

初始化分为静态初始化和动态初始化

1.静态初始化

初始化不指定元素个数

int[] array1 = new int[]{0,1,2,3,4,5,6,7,8,9};
double[] array2 = new double[]{1.0, 2.0, 3.0, 4.0, 5.0};
String[] array3 = new String[]{"hell", "Java", "!!!"};

2.动态初始化

在创建数组时，直接指定数组中元素的个数

int[] array = new int[10];

• 静态初始化会根据后面的内容指定数组大小
• 静态初始化可以简写，省去后⾯的newT[]

没有初始化数组里面就存的默认值

类型	默认值
byte	0
short	0
int	0
long	0
float	0.0f
double	0.0
char	/u0000
boolean	false

*引用类型的默认值是null

2.3 数组的使用

数组在内存中是⼀段连续的空间，空间的编号都是从0开始的，依次递增，该编号称为数组的下标，数组可以通过下标访问其任意位置的元素

int[]array = new int[]{10, 20, 30, 40, 50};
System.out.println(array[0]);
System.out.println(array[1]);
System.out.println(array[2]);
System.out.println(array[3]);
System.out.println(array[4]);
//也可以通过[]对数组中的元素进⾏修改
array[0] = 100;
System.out.println(array[0]);

如果下标不在数组的范围里就会越界，抛出 java.lang.ArrayIndexOutOfBoundsException 异常

int []arr1 = new int[]{1,2,3,4,5,6,7,8,9};
        for (int i = 0; i < arr1.length; i++) {
            System.out.println(arr1[i]);
}

数组中可以通过.length获取数组的长度

也可以使⽤for-each遍历数组

int[] array = {1, 2, 3};
for (int x : array) {
    System.out.println(x);
}

2.4 数组是引用类型

初识JVM内存分布

• 程序计数器(PCRegister):只是⼀个很⼩的空间,保存下⼀条执⾏的指令的地址
• 虚拟机栈(JVMStack):与⽅法调⽤相关的⼀些信息，每个⽅法在执⾏时，都会先创建⼀个栈帧，栈帧中包含有：局部变量表、操作数栈、动态链接、返回地址以及其他的⼀些信息，保存的都是与⽅法执⾏时相关的⼀些信息。⽐如：局部变量。当⽅法运⾏结束后，栈帧就被销毁了，即栈帧中保存的数据也被销毁了。
• 本地⽅法栈(NativeMethodStack):本地⽅法栈与虚拟机栈的作⽤类似.只不过保存的内容是 Native⽅法的局部变量.在有些版本的JVM实现中(例如HotSpot),本地⽅法栈和虚拟机栈是⼀起的
• 堆(Heap):JVM所管理的最⼤内存区域.使⽤new创建的对象都是在堆上保存(例如前⾯的 new int[]{1, 2, 3} )，堆是随着程序开始运⾏时⽽创建，随着程序的退出⽽销毁，堆中的数据只要还有在使⽤，就不会被销毁。
• ⽅法区(MethodArea):⽤于存储已被虚拟机加载的类信息、常量、静态变量、即时编译器编译后 的代码等数据.⽅法编译出的的字节码就是保存在这个区域

2.5 引用变量

基本数据类型创建的变量，称为基本变量，该变量空间中直接存放的是其所对应的值； ⽽引⽤数据类型创建的变量，⼀般称为对象的引⽤，其空间中存储的是对象所在空间的地址。

引⽤变量并不直接存储对象本⾝，可以简单理解成存储的是对象在堆中空间的起始地址。通过该地址，引⽤变量便可以去操作对象。有点类似C语⾔中的指针，但是Java中引⽤要⽐指针的操作更简单。

2.5 null

null 的作⽤类似于C语⾔中的NULL(空指针),都是表⽰⼀个⽆效的内存位置.因此不能对这个内存进⾏任何读写操作.⼀旦尝试读写,就会抛出NullPointerException

2.6 Arrays与数组练习

数组转字符串

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5};
        String newArr = Arrays.toString(arr);
        System.out.println(newArr);
    }
}

数组拷贝

// newArr和arr引⽤的是同⼀个数组
// 因此newArr修改空间中内容之后，arr也可以看到修改的结果

int[] arr = {1,2,3,4,5};
int[] newArr = arr;
newArr[0] = 10;
System.out.println("arr"+Arrays.toString(arr));//arr[10, 2, 3, 4, 5]

//使⽤Arrays中copyOf⽅法完成数组的拷⻉：
// copyOf⽅法在进⾏数组拷⻉时，创建了⼀个新的数组
// arr和newArr引⽤的不是同⼀个数组
arr[0] = 1;
newArr = Arrays.copyOf(arr,arr.length);
System.out.println("newArr"+Arrays.toString(newArr));
arr[0] = 10;
System.out.println("newArr"+Arrays.toString(newArr));

//拷贝某个范围
int[] arr2 = Arrays.copyOfRange(arr,2,4);
System.out.println("arr2"+Arrays.toString(arr2));//arr2[3, 4]

注意：数组当中存储的是基本类型数据时，不论怎么拷⻉基本都不会出现什么问题，但如果存储的是引⽤数据类型，拷⻉时需要考虑深浅拷⻉的问题。

自己版本的数组拷贝

public static int[] copyOf(int[] arr) {
    int[] ret = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        ret[i] = arr[i];
    }
    return ret;
}

数组练习

顺序查找数组元素

给定⼀个数组,再给定⼀个元素,找出该元素在数组中的位置.

 public static void main(String[] args) {
        int[] arr1 = {1,2,3,4,5,6,8,9,10};
        System.out.println(find(arr1, 5));//4
}
    public static int find(int[] arr,int k) {
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] == k) {
                return i;
            }
        }
        return -1;
}

二分查找

针对有序数组采用二分查找，也叫折半查找

public static void main(String[] args) {
        int[] arr1 = {1,2,3,4,5,6,8,9,10};
        System.out.println(binarySearch(arr1, 6));
}

public static int binarySearch(int[] arr,int k) {
        int left = 0;
        int right = arr.length;
        while (left <= right) {
            int mid = left + (right - left)/2;
            if(arr[mid] < k) {
                left = mid + 1;
            }else if(arr[mid] > k) {
                right = mid -1;
            }else {
                return mid;
            }
        }
        return -1;//没找到
}

冒泡排序

假设排升序：

1. 将数组中相邻元素从前往后依次进⾏⽐较，如果前⼀个元素⽐后⼀个元素⼤，则交换，⼀趟下来后最⼤元素就在数组的末尾

2. 依次从上上述过程，直到数组中所有的元素都排列好

public static int[] bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flag = false;  // 标志：本轮是否发生交换

            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    flag = true;   // 发生了交换
                }
            }

            // 如果本轮没有交换，说明已经有序，提前结束
            if (!flag) {
                break;
            }
        }
        return arr;
}

冒泡排序性能较低.Java中内置了更⾼效的排序算法

public static void main(String[] args) {
        int[] arr = {9, 5, 2, 7};
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
}

数组逆序

思路

设定两个下标,分别指向第⼀个元素和最后⼀个元素.交换两个位置的元素. 然后让前⼀个下标⾃增,后⼀个下标⾃减,循环继续即可.

public static void reverse(int[] arr) {
    int left = 0;
    int right = arr.length - 1;
    while (left < right) {
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
        left++;
        right--;
    }
}

3，二维数组

基本语法

数据类型[][] 数组名称 = new 数据类型 [⾏数][列数] { 初始化数据 };

行不可以省略列能省略

int[][] arr = {
                {1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12}
};
        for (int row = 0; row < arr.length; row++) {
            for (int col = 0; col < arr[row].length; col++) {
                System.out.printf("%d\t", arr[row][col]);
            }
            System.out.println("");
}

不规则二维数组

⼆维数组的列在定义的时候，没有确定

int[][] array = new int[2][];
array[0] = new int[3];
array[1] = new int[5];