java递归

1.通过递归计算5的阶乘

TestDiGui.java

//通过递归计算5的阶乘
public class TestDiGui {
	public static void main(String[] args) {
		System.out.println(m(5));	//结果为120
	}
	public static int m(int n) {
		if(n == 1) return 1;
		else return n*m(n-1);		
	}
}

方法调用图：

 
 

2.通过递归方法计算fibnacci数列

TestFib.java

//通过递归计算斐波那契数列
//fibnacci f1=1,f2=1,f3=2,f4=3,f5=5,...,fn=f(n-1)+f(n-2);(n>2)
public class TestFib {
	public static void main(String[] args) {
		System.out.println(f(5));	//结果为5
	}	
	public static long f(int n) {
		if(n == 1 || n == 2){
			return 1;
		} else {
			return f(n-1)+f(n-2);	
		}	
		
	}
}

 递归方法调用图：

 

 3.通过非递归计算斐波那契数列

Fib.java

//通过非递归计算斐波那契数列
//fibnacci f1=1,f2=1,f3=2,f4=3,f5=5,...,fn=f(n-1)+f(n-2);(n>2)
public class Fib {
	public static void main(String[] args) {
		System.out.println(f(5));//结果5	
	}	
	
	public static long f(int n) {
		if(n == 1 || n ==2) {
			return 1;
		}
		long f1 = 1L;
		long f2 = 1L;
		long f = 0;
		
		for(int i=0; i < (n-2); i++) {
			f = f1 + f2;
			f1 = f2;
			f2 = f;
		}
		
		return f;
		
	}
}