递归问题，案例（1-100的和，斐波那契数列等）（Java）

递归方法（recursion）：自己调用自己
递归一定要向已知的方向递归，否则这种递归就变成了无穷递归，类似于死循环

	//计算1-100之间所有自然数的和
	public int getSum(int n) {
		if(n == 1) {
			return 1;
		}else {
			return n + getSum(n-1);
		}
	}
	
	//已知有一个数列：f(0)=1，f(1)=4,f(n+2)=2*f(n+1)+f(n).n是大于0的整数，求f(10)
	public int getF(int n) {
		if(n==0) {
			return 1;
		}else if(n==1) {
			return 4;
		}else {
			return 2*getF(n-1)+getF(n-2);
		}
	}
	
	//斐波那契数列（一个数字等于前两个位置上的数字之和）：输入一个n，求出第n个斐波那契数列的值。
	//斐波那契数列：1 1 2 3 5 8 13  21 34 55
	public int Fibonacci(int n) {
		if(n==1) {
			return 1;
		}else if(n==2) {
			return 1;
		}
		else {
			return Fibonacci(n-1)+Fibonacci(n-2);
		}
	}