一：Java中的方法

（1）什么是方法

方法：Java中方法就是一个代码片段，它类似于 C 语言中的 “函数”。作用有：

• 能够模块化的组织代码
• 做到代码被重复使用 ，一份代码可以在多个位置使用
• 让代码更好理解更简单
• 直接调用现有方法开发，不必重复造轮子

（2）方法定义

在Java中，定义一个方法的基本格式如下，注意

• 修饰符：现阶段直接使用public static固定搭配即可
• 返回值类型：如果方法有返回值，则返回值类型必须要与返回的实体的类型一致；如果没有返回值，必须写成void
• 方法名字：采用“小驼峰”方式命名
• 参数列表：如果方法没有参数则什么都不写；如果有参数，则需要指明参数类型，多个参数之间使用逗号隔开
• 方法体：就是方法内部需要执行的语句，实现方法功能
• 在Java中：方法必须写在类中、方法不能嵌套定义、没有所谓的“声明方法”

修饰符 返回值类型 方法名称([参数类型 形参1,参数类型 形参2...]){
	方法体代码;
	[return 返回值];
}

//例子：两个整数相加
public static int add(int x, int y){
	int ret = x + y;
	return ret;
}
1
2
3
4
5
6
7
8
9
10

（3）方法调用

使用方法时称之为方法调用。例如下面的例子：计算1!+2!+3!+4!+5!

public class TestDemo {
    public static void main(String[] args) {
        int sum = 0;
        for(int i = 1; i <= 5; i++){
            sum += fac(i);
        }
        System.out.println("1!+2!+3!+4!+5!=" + sum);
    }
    //计算的n!
    public static int fac(int n){
        System.out.print("计算" + n + "!=：");
        int ret = 1;
        for(int i = 1; i <= n ; i++){
            ret*=i;
        }
        System.out.println(ret);
        return ret;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

（4）实参和形参的关系

A：实参和形参是什么

• 实际参数（实参）：调用方法时传入的参数
• 形式参数（形参）：定义方法时的参数，形参名任意

B：传值和传引用

在Java中，实参和形参分别占据不同的内存空间，方法被调用后会自动为形参开辟空间，两片空间没有任何关系，方法调用完毕形参所在空间就会被销毁。在上面的例子，实参只是把形参的值复制了一份给了形参，形参不会影响到实参

例如下面的例子中，swap方法无法实现变量交换，它仅仅交换的是形参

public class TestDemo {
    public static void main(String[] args) {
        int a = 10;
        int b = 20;
        swap(a, b);
        System.out.println("a="+a+" b="+b);
    }
    public static void swap(int x, int y){
        int temp = x;
        x = y;
        y = temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

对于上面的基本类型，形参是实参的拷贝，所以传参时属于 传值调用；而对于引用类型，形参从某种方面来讲就是实参，所以传参时属于 传引用调用，此时对形参的修改则会直接反馈在实参上（后面再讲）

二：方法重载

（1）概念

• 可对照C++中的函数重载学习：C++快速入门之函数重载

方法重载：Java中允许多个同名方法同时存在。满足以下要求时构成方法重载

• 方法名称相同
• 形参列表不同（类型、个数、顺序满足其一即可）
• 返回值不做要求（但两个或多个方法仅仅因为返回值类型不同是不能构成重载的）

如下有三个同名方法add()构成重载，编译器在编译代码时，会对实参类型进行推演，根据推演的结果来确定调用哪个方法

public class TestDemo {
    public static void main(String[] args) {
        int a = add(1, 2);
        double b = add(3.14, 5.27);
        double c = add(1, 1.98, 2);
        System.out.println(a);
        System.out.println(b);
        System.out.println(c);
    }
    public static int add(int x, int y){
        return x + y;
    }
    public static double add(double x, double y){
        return x + y;
    }
    public static double add(int x, double y, int z){
        return x + y;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

（2）实现原理

• 可对照C++中的函数重载学习：C++快速入门之函数重载

之所以可以实现这样的功能，是因为编译器在编译时会对原有方法名进行修饰，修饰规则为：方法全路径名+参数列表+返回值类型，以此构成方法完整的名字

这里，对上述字节码文件执行反汇编：javap -v TestDemo.class后可查看到如下信息

三：递归

（1）递归基本概念

递归：递归是解决复杂问题的一种常用方法，其本质就是把问题分解成为规模更小的、具备与原问题有着相同解法的问题，直至不能分解为止。从表象上则有一种自己调用自己的感觉。递归必须满足以下两个条件

• 能够经过递归调用来缩小问题规模，且新问题与原问题有着相同的形式：例如求5！，我们的思路是5！=5×4×3×2×1，但仔细观察：5！=5×4！，这里4！就是5！的一个分解
• 必须有一个结束条件（递归出口）：如果没有将会引发无穷递归（编译器会报出stackoverflow的错误）

如下是求N！的递归算法

public class TestDemo {
    public static int recur(int N){
        if(N == 1){//递归出口
            return 1;
        }
        return N * recur(N-1);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int ret = recur(N);
        System.out.println(N + "!=" + ret);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

（2）以“斐波那契数列”为例探究递归

递归、状态转移、动态规划这些概念总是分不开的，所以这里以动态规划算法为例探究一下递归的思想

---

LeetCode 509：斐波那契数列

暴力递归

斐波那契数列是一个典型的递归题目，它的递归写法如下

class Solution {
public:
    int fib(int n) 
    {
        if (n==0) return 0;
        if (n==1 || n==2) return 1;
        return fib(n-1)+fib(n-2);
    }
};
1
2
3
4
5
6
7
8
9

题目可以通过，但是时间高的吓人

递归问题本质就是二叉树的问题，所以在递归的过程中就是在遍历一颗二叉树，所以这种写法对应的递归树是这样的

很显然，想要计算fib(20)，就先要计算fib(19)和fib(18)，计算fib(19)又要计算fib(18)和fib(17)…可以看出图中的f(18),f(17)很显然是不需要计算的，虽然图中只画出了一点，但是你应该明白，这颗递归树要是完全展开，那是很恐怖的。所以这个算法极其低效

“备忘录”递归解法

既然耗时的原因是因为重叠子问题太多，那么不如这样：把fib(18)计算完之后，存储在一个备忘录中，下次只要需要求解fib(18)，直接从备忘录里面拿多好。
而实现备忘录，我们更多用数组，当然你也可以用哈希表，道理是一样的。

class Solution {
public:
    int back(vector<int>& memory,int n)
    {
        if(n==1 || n==2) return 1;
        if(memory[n]!=0) return memory[n];//一旦对应位置不等于0，表示已经计算过了，立马直接返回结果即可

        return back(memory,n-1)+back(memory,n-2);

    }

    int fib(int n) 
    {
        if (n==0) return 0;
        vector<int> memory(n+1,0);//设立一个备忘录，初始状态设置为0，0表示该位置的元素没有被记录在备忘录上
        return back(memory,n);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

继续观察这种算法的递归树，如下，你可以很明显的发现，这种带备忘录的解法就是我们经常说的“剪枝”操作，以下把一颗非常冗余的树修剪的很干净，或者说就是减少了重叠子问题

如下，很明显它的时间复杂度要低

递归会引出两种解决问题的方法

• 自顶向下（递归做法）：从一个原始的问题，也就是规模较大的问题，比如说fib(20)，逐步向下分解，分解到很小的规模,一直分解到再不能分解为止，比如fib(1)和fib(2)这两个base case
• 自底向上（动态规划做法）：反过来，从最下面，最简单的情况如上，进行反推得到结果

反递归做法-动态规划

我们把上面的备忘录变成一个dp数组，通过dp数组不断迭代向上求解。

class Solution {
public:
    int fib(int n) 
    {
        if(n==0) return 0;
        if(n==1 || n==2) return 1;
        vector<int> dp(n+1,0);

        //最简单的情况，base case
        dp[1]=1;
        dp[2]=1;
        for(int i=3;i<=n;i++)
        {
            dp[i]=dp[i-1]+dp[i-2];
        }

        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

你会很明显发现，这样的结局效率非常的高

同时这种算法对应的图和带备忘录的递归算法的那张图结果相反

状态转移方程

其实在这个过程中，我们已经不知不觉的使用了状态转移方程。如下，

你可以把f(n)当作一个状态，而这个状态n是由状态n-1和状态n-2进行相加操作转移过来的，仅此而已。所以代码中的dp[i]=dp[i-1]+dp[i-2]就是这个意思

那么如何得出状态转移方程呢？其实完全依赖的就是咋们的暴力解法，暴力解法代表的就是状态转移方程，一旦动态规划的题目中你能写出暴力解法，那么剩余的操作无非就是备忘录或dp数组优化了。也就是先自顶向下，再自底向上

关于斐波那契数列一个极限解法

仔细观察你会发现，当前状态仅仅和前两个状态有关，而前面无关，所以我们可以优化空间，不采用数组，直接两个变量，交替保存

class Solution {
public:
    int fib(int n) 
    {
        if (n==0) return 0;
        if (n==1 || n==2) return 1;
        int prev=1;int curr=1;
        for(int i=3;i<=n;i++)
        {
            int sum=prev+curr;
            prev=curr;
            curr=sum;
        }
        return curr;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16