public class Fibonacci {
	

	
	public static void main(String[] args) {
//		System.out.println(fib_chaining(10000));
		hanoi(3, "start", "temp", "goal");
	}
	
	public static void hanoi(int n, String start, String temp, String goal) {
		if (n == 0) return;
		hanoi(n-1, start, goal, temp);
		System.out.println("move " + n + " from " + start + " to " + goal);
		hanoi(n-1, temp, start, goal);
	}
	
	public static long fib(int n) {
		if (n == 0) return 1;
		if (n == 1) return 1;
		return fib(n-1) + fib(n-2);
	}	
	
	public static long fib_chaining(int n) {
		return fib_chaining_helper(1, 1, n);
	}
	
	private static long fib_chaining_helper(long current, long next, int n) {
		if (n == 1) return current;
		return fib_chaining_helper(next, current + next, n - 1);
	}
	
	public static long fib_array(int n) {
		long[] fibs = new long [n+1];
		fibs[1] = 1;
		fibs[2] = 1;
 		return fib_array_helper(n, fibs);
	}
	
	private static long fib_array_helper(int n, long[] fibs) {
		if (n == 1) return fibs[1];
		if (n == 2) return fibs[2];
		if (fibs[n] == 0) fibs[n] = fib_array_helper(n-1, fibs) + fib_array_helper(n-2, fibs);
		return fibs[n];
	}

}