import java.math.BigInteger;


public class Recursion {
	
	public static void main(String[] args){
//		foo(1);
//		System.out.println(factorial(5000));
		System.out.println(fibonacci(10));
	}
	
	public static void foo(int i){
		if (i < 10) {
			System.out.println(i);
			foo(i+1);
		}
	}
	
	public static BigInteger factorial(int n){
		if (n == 0) return new BigInteger("1");
		if (n == 1) return new BigInteger("1");
		BigInteger temp = BigInteger.valueOf(n);
		return temp.multiply(factorial(n - 1));
	}
	
	public static BigInteger fibonacci(int n){
		if (n == 1) return new BigInteger("1");
		if (n == 2) return new BigInteger("1");
		BigInteger temp = fibonacci(n - 1);
		return temp.add(fibonacci(n - 2));
	}

}