/**
 * Calculate Fibonacci using top-down and bottom-up.
 *   @author Dave Reed
 *   @version 10/25/24
 */
public class Fibonacci {

	/**
	 * Calculates the nth Fibonacci number using divide-and-conquer.
	 *   @param n the desired number in the sequence
	 *   @return nth Fibonacci number
	 */
	public static int fibonacciTopDown(int n) {
		if (n <= 1) {
			return 1;
		} else {
			return fibonacciTopDown(n-1) + fibonacciTopDown(n-2);
		}
	}

	/**
	 * Calculates the nth Fibonacci number using dynamic programming.
	 *   @param n the desired number in the sequence
	 *   @return nth Fibonacci number
	 */
	public static int fibonacciBottomUp(int n) {
		int prev = 1, current = 1;
		for (int i = 1; i < n; i++) {
		    int next = prev + current;
		    prev = current;
		    current = next;
		}
		return current;

	}

	///////////////////////////////////////////////////////////////////////////
	
	public static void main(String[] args) {
		for (int n = 0; n <= 10; n++) {
		    System.out.println(fibonacciBottomUp(n) + " " + fibonacciTopDown(n));
		}
	}

}