清溪算法 2020-05-25
a(){
a();
}
/* 方法递归 */ public class MethodDG { public static void main(String[] args) { System.out.println("main begin"); doSome(); System.out.println("main over"); } /*以下的代码片段虽然只有一份,但是可以被重复调用,并且只要调用doSome方法就会在栈内存中分配一块所属的内存空间 * */ public static void doSome() { System.out.println("begin"); doSome();//这行代码不结束,下一行程序是不能被执行的 System.out.println("over"); } }
以上的程序运行的时候肯定会发生如下错误:java.lang.StackOverflowError(这是错误不是异常),栈内存溢出错误,错误发生无法挽回,只有一个结果,就是 JVM 会停止工作。结论:
public class SumT1 { public static void main(String[] args) { int n = 5; int sum = 0; for (int i = 0; i <= n; i++) { sum = sum + i; } System.out.println(sum); } }
public class SumT1 { public static void main(String[] args) { System.out.println(sum(5)); } public static int sum(int n){ int result = 0; for (int i=1;i<=n;i++){ result +=i; } return result; } }
public class SumT2 { public static void main(String[] args) { System.out.println(sum(4)); } public static int sum(int n) { if (n==1){ return 1; } return n+sum(n-1); } }
我们分析下问什么按照以上代码即可以实现递归:
很明显我们应该采取第二种方式进行加和。还要注意递归的时候需要有结束条件,不然会发生栈内存溢出错误。所以我们第一步确认递归结束条件:如果 n==1,此时结束递归,将此时的值进行返回。
如果没有满足递归条件则此时按照如下计算逻辑进行计算:
因此此时的递归逻辑应该是:4+3+2+1=10,即将我们需要的计算结果进行了返回。
例如:5 的阶乘:5*4*3*2*1
public class Factorial01 { public static void main(String[] args) { int n = 5; int retValue = method(n); System.out.println(retValue); } public static int method(int n) { int result = 1;//初始值为1 for (int i = n; i > 0; i--) {//此时的 i 的值依次为:5 4 3 2 1 result *= i; } return result; } }执行结果为:120
public class Factorial02 { public static void main(String[] args) { int n = 5; int retValue = method(n); System.out.println(retValue); } public static int method(int n){ int result = 1; if (n==1){ return 1; } return n*method(n-1); } }此时计算结果为:120
如果我们用一个图来描述上述递归过程类似如下的调用过程:
我们将上述图逆时针旋转 90 度会发现,这其实就是一个栈,main 方法最先调用,但是处于栈底的位置,因此最后出结果,递归结束条件处于栈顶,因而最先出计算结果。