JavaSE:方法的使用及递归

一、方法概念及使用

方法就是一个代码片段. 类似于 C 语言中的 "函数"。

方法的定义

语法格式

// 方法定义
修饰符 返回值类型 方法名称([参数类型 形参 …]){
方法体代码;
[return 返回值];
}

例如：写一个方法实现判断是否为闰年

public class Test{
public static void main(String[] args){
int year = 2008;
boolean ret = isLeapYear(year);
if(ret == true){
System.out.println("是闰年!");
}else{
System.out.println("不是闰年!");
}
}
public static boolean isLeapYear(int year){
if(year % 4 == 0 && year %100 != 0 || year % 400 == 0){
return true;
}
return false;
}
}

【注意事项】

方法调用的执行过程

调用方法—>传递参数—>找到方法地址—>执行被调方法的方法体—>被调方法结束返回—>回到主调方法继续往下执行

【注意事项】

• 定义方法的时候, 不会执行方法的代码. 只有调用的时候才会执行.
• 一个方法可以被多次调用.

实参与形参的关系

在Java 中的形参和实参与 C语言的类似

我们在调用方法的时候，传递的参数就是实参，它是一个确定的值;而被调用的方法的括号内就是形参，形参的名字可以随意取，对方法都没有任何影响，形参只是方法在定义时需要借助的一个变量，用来保存方法在调用时传递过来的实参，方法调用结束后，形参就会被回收

例如：

public static void main(String[] args){

getSum(10); // 10是实参,在方法调用时，形参N用来保存10
getSum(100);// 100是实参，在方法调用时，形参N用来保存100
}
public static int getSum(int N){   // N是形参
   return (1+N)*N / 2;
}
//又比如：
add(2, 3);   // 2和3是实参，在调用时传给形参a和b

public static int add(int a, int b){
   return a + b;
}

注意：

在Java中，实参的值永远都是拷贝到形参中，形参和实参本质是两个实体

例如：实现两个整型变量的交换

public class TestMethod {
public static void main(String[] args) {
int a = 10;
int b = 20;
swap(a, b);
System.out.println("main: a = " + a + " b = " + b);
}

public static void swap(int x, int y) {
int tmp = x;
x = y;
y = tmp;
    System.out.println("swap: x = " + x + " y = " + y);
}
}

但是，在swap函数交换之后，形参x和y的值发生了改变，但是main方法中a和b还是交换之前的值，即没有交换成功

// 运行结果

swap: x = 20 y = 10

main: a = 10 b = 20

【原因分析】

实参a和b是main方法中的两个变量，其空间在main方法的栈(一块特殊的内存空间)中，而形参x和y是swap方法中 的两个变量，x和y的空间在swap方法运行时的栈中

因此：实参a和b 与 形参x和y是两个没有任何关联性的变量， 在swap方法调用时，只是将实参a和b中的值拷贝了一份传递给了形参x和y，因此对形参x和y操作不会对实参a和b 产生任何影响

即对于基础类型来说, 形参的改变不会影响实参，形参相当于实参的拷贝. 即 传值调用

那么按照C语言的解决方式：就是 传址调用 ，在给函数传参的时候，传地址&，然后用指针变量来接收（通过&取地址操作来改变实参的值）

但是，在Java当中是拿不到栈上的局部变量的地址的，也没有指针的概念

【解决办法】: 传引用类型参数 (包括字符串和数组，例如数组来解决这个问题)

（此代码等学习完数组就能看懂）

public class TestMethod {
public static void main(String[] args) {
int[] arr = {10, 20};
swap(arr);
System.out.println("arr[0] = " + arr[0] + " arr[1] = " + arr[1]);

}

public static void swap(int[] arr) {
int tmp = arr[0];
arr[0] = arr[1];
arr[1] = tmp;
}
}

// 运行结果

arr[0] = 20 arr[1] = 10

没有返回值的方法

方法的返回值是可选的. 有些时候可以没有的，没有时返回值 类型必须写成void

示例：

public class Test {
public static void main(String[] args) {
int a = 10; int b = 20; print(a, b);
}

public static void print(int x, int y) {
System.out.println("x = " + x + " y = " + y);
}
}

另外，上面的交换两个整数的方法,就是没有 返 回 值 的

二、方法重载

为什么需要方法重载

当我们想要写一个方法实现两个数的相加：

public static int add(int a,int b){
return a+b;
}
public static void main5(String[] args) {
int x = 1;
int y = 2;
int ret = add(x,y);

double d1 = 1.0;
double d2 = 2.0;
double ret1 = add(d1,d2);
System.out.println(ret1);
}

运行起来时，发现报错了：

// 编译出错

Test.java:13: 错误: 不兼容的类型: 从double转换到int可能会有损失                

double ret2 = add (a2,b2) ;

             ^

由于参数类型不匹配，所以不能直接使用现有的 add 方法

一般解决方式都是每个类型创建一个方法并取一个专门的方法名：

public static void main5(String[] args) {
int x = 1;
int y = 2;
int ret = addInt(x,y);
System.out.println(ret);

double d1 = 1.0;
double d2 = 2.0;
double ret1 = addDouble(d1,d2);
System.out.println(ret1);
}
public static int addInt(int a,int b){
return a+b;
}
public static double addDouble(double a,double b){
return a+b;
}

上述代码确实可以解决问题，但不友好的地方是：需要提供许多不同的方法名，而取名字本来就是让人头疼的事情。那能否将所有的名字都给成 add 呢？

方法重载概念

在自然语言中，经常会出现“一词多义”的现象，比如，“方便”，可以表示内急，表示方便面等

一个词语如果有多重含义，那么就说该词语被重载了，具体代表什么含义需要结合具体的场景。 在Java中方法也是可以重载的。

在Java中，如果多个方法的名字相同，参数列表不同，则称该几种方法被重载了

public class Test{
public static void main(String[] args){
int a = 10;
int b = 20;
int ret = add(a,b); //调用add(int, int)
System.out.println(ret);

double d1 = 1.0;
double d2 = 2.0;
double ret1 = add(d1,d2);//调用add(double, double)
System.out.println(ret1);
}

public static int add(int a, int b){
return a+b;
}
public static double add(double a, double c){
return a+b;
}
}

当我们写完add方法不同类型时，每次我们想要调用add方法，就会浮现add的方法重载：

注意：重载的条件

注意：两个方法如果仅仅只是因为返回值类型不同，是不能构成重载的

注意:参数列表的类型顺序不同必须是不同类型的参数顺序不同，否则会报错

方法签名

在同一个作用域中不能定义两个相同名称的标识符。比如：方法中不能定义两个名字一样的变量，那为什么类中就可以定义方法名相同的方法呢？（即方法重载实现方式）—— 通过方法签名实现

方法签名即：经过编译器编译修改过之后方法最终的名字。

具体方式：方法全路径名+参数列表+返回值类型，构成方法完整的名字。

方法签名的关键要素：

例如以下的代码：

public class TestMethod {
   public static int add(int x, int y){
       return x + y;
  }

   public static double add(double x, double y){
       return x + y;
  }

   public static void main(String[] args) {
       add(1,2);
       add(1.5, 2.5);
  }
}

上述代码经过编译之后，然后使用JDK自带的javap反汇编工具查看，具体操作：

以整型类型为例：

总结

方法重载的实现是编译器通过方法签名生成唯一的方法标识符

方法签名中的一些特殊符号说明：

三、递归

一个方法在执行过程中调用自身, 就称为 "递归".

递归相当于数学上的 "数学归纳法", 有一个起始条件, 然后有一个递推公式.

例如, 我们求 N!

起始条件: N = 1 的时候, N! 为 1. 这个起始条件相当于递归的结束条件.

递归公式: 求 N! , 直接不好求, 可以把问题转换成 N! => N * (N-1)!

递归的必要条件：

递归执行过程分析

递归的程序的执行过程不太容易理解, 要想理解清楚递归, 必须先理解清楚 "方法的执行过程", 尤其是 "方法执行结束 之后, 回到调用位置继续往下执行".

代码示例：递归求 N 的阶乘

public static void main(String[] args){
int n = 5;
int ret = factor(n);
System.out.println("ret=" + ret);
}

public static int factor(int n){
System.out.println("函数开始, n = " + n);
if(n == 1){
System.out.println("函数结束, n = 1 ret = 1");
return 1;
}
int ret = n * factor(n-1); // factor 调用函数自身
System.out.println("函数结束, n = " + n + " ret = " + ret);
return ret;
}

// 执行结果

函数开始, n = 5

函数开始, n = 4

函数开始, n = 3

函数开始, n = 2

函数开始, n = 1

函数结束, n = 1 ret = 1

函数结束, n = 2 ret = 2

函数结束, n = 3 ret = 6

函数结束, n = 4 ret = 24

函数结束, n = 5 ret = 120

ret = 120

执行过程图

程序按照序号中标识的 (1) -> (8) 的顺序执行

关于 "调用栈"

方法调用的时候, 会有一个 "栈" 这样的内存空间描述当前的调用关系. 称为调用栈. 每一次的方法调用就称为一个 "栈帧", 每个栈帧中包含了这次调用的参数是哪些, 返回到哪里继续执行等信息.

递归的练习

按顺序打印一个数字的每一位

例如 1234 打印出 1 2 3 4

思路：使用 /10 ，%10 的方法

结束条件（即起始条件）：n < 10(当n小于10的时候，任何数字 /10 都是它本身，直接打印即可)

递推公式：print(n / 10)  ,   n %10  

public static void main(String[] args){
System.out.println(print(1234));
}

public static void print(int n){
if(n < 10){
System.out.println(n);
return;
}
print(n / 10);
System.out.println(n % 10);
}

执行过程：

递归求 1 + 2 + 3 + … + 10

思路：求1+到10 ——> 就是 1+2+3+……+n  的问题，即 我们可以利用公式 n + (n-1) 来求解

结束条件：n == 0（n == 1）

递推公式：n + sum(n-1)

public static void main(String[] args){
System.out.println(sum(10));
}

public static int sum(int n){
if(n == 0){
return 0;
}
return n + sum(n-1);//55
}

执行过程：

写一个递归方法，输入一个非负整数，返回组成它的数字之和

例如，输入 1729, 则应该返回 1+7+2+9，它的和是19

思路：/10  ，%10

结束条件：n < 10

递推公式：fun(n /10) + n % 10

public static void main(String[] args){
System.out.println(fun(1729));
}

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

执行过程：

求斐波那契数列的第 N 项

斐波那契数列，又称黄金分割数列

斐波那契数列指的是这样一个数列：

这个数列从第3项开始，每一项都等于前两项之和

斐波那契数列被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n – 1)+F(n – 2)

递推求斐波那契数列的第N项

结束条件：n < 3

递推公式：fib(n – 1) + fib(n – 2)

public static void main(String[] args){

System.out.println(fib(1));//1
System.out.println(fib(5));//5
System.out.println(fib(10));//55
System.out.println(fib(40));//102334155
}

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

执行过程：

递归过程拆解（从顶层向下计算）：

(当计算完左分支后，再计算右分支)

最终结果：斐波那契数列第五项为 5

我们看图可以知道，其实使用递归求斐波那契数列效率并不高，因为它在递归的过程有许多重复的地方（重复计算了F(3),F(2),F(1)），使用循环求解更高效

循环求斐波那契数列的第N项

思路：在 fib 方法内创建三个变量f1,f2,f3，表示第n-1项，第n项，第n+1项，给它们初始化都为1

使用for循环遍历，初始值设为i=3,即如果n满足此条件即可进入循环，进行前两项相加等于第n项的值f3，求完后将原本的f2赋值给f1，f3赋值给f2，以便进行下一次循环，最后返回f3；如果不满足循环条件，则直接返回f3初始化的值（即n是第1/2项）

public static void main(String[] args){

System.out.println(fib(1));//1
System.out.println(fib(5));//5
System.out.println(fib(10));//55
System.out.println(fib(40));//102334155
}

public static int fib(int n){
int f1 = 1;
int f2 = 1;
int f3 = 1;
for(int i = 3;i <= n; i++){
f3 = f1 + f2;
f1 = f2;
f2 = f3;
}
return f3;
}