4、Java递归
一 递归
递归：在一个方法的内部对自身进行调用
如下一段代码
public class TestRecursion {
public static void main (String[] args) {
System.out.println(method(5));
}
public static int method(int n) { //返回值的类型为int类型
if (n == 1) {
return 1;
}
else {
return n*method(n-1);
}
}
}
分析，如下图所示：
当n=3时，return 3*method(3-2)
接着，return 2*method(2-1)
接着，当n为1时，return 1
返回1给method(2-1)，即method(2-1)=1
继续返回，method(3-2)=2*1=2
所以，当n等于3时，method(3)=3*2=6
方法结束
如下面一段代码
public class Fib {
public static void main(String[] args) {
System.out.println(f(5));
}
public static int f(int n) {
if (n == 1 || n == 2) {
return 1;
} else {
return f(n - 1) + f(n - 2);
}
}
}
内存分析：
上述一段代码，进行内存分析。当n为5时，首先
f(4) + f(3)
而f(4)依然没有返回值，f(4)继续展开
f(3) + f(2)
f(3)没有返回值，f(3)继续展开
f(2) + f(1)
f(2)有返回值，当n等于2或者n等于1的时候，返回值为1，所以f(2)=1返回
f(1)有返回值，所以f(1)=1返回
f(2)有返回值，所以f(2)=1返回
此时f(4)的值为3，返回f(5)
然后f(5)继续调用f(3)，f(3)继续展开，最终返回值为2
所以f(5)=3+2
f(5)被main方法调用，为5，程序结束
/*
Fibonacci数列问题，即 1,1,2,3,5,8,13,...
即下一个数是前面两个数的和
*/
//测试Fibonacci数列问题，使用非递归方式第40个Fibonacci数是多少
public class TestFib {
public static void main(String[] args) {
System.out.println(f(40));
}
public static long f(int index) {
if (index == 1 || index == 2) {
return 1;
}
long f1 = 1L;
long f2 = 1L;
long f = 0;
for (int i=1;i<=index-2;i++) {
f = f1 + f2;
f1 = f2;
f2 = f;
}
return f;
}
}