package recursion;

import java.util.*;

/*
 * @author Talha K.
 * An iterative method for calculating Fibonacci numbers in O(n) time,
 * according to the memoization technique of caching previously computed values.
 */
public class GitFibonacci {

	private ArrayList<Integer> fibNums;

	public GitFibonacci(){
		fibNums = new ArrayList<Integer>();
		fibNums.add(1);
		fibNums.add(1);
		assert(fibNums.size() == 2);
	}

	public int getFibNum(int n){

		if (n > fibNums.size()){
			int prevNum = fibNums.get(fibNums.size() - 1);
			int prevPrevNum = fibNums.get(fibNums.size() - 2);

			int numIterations = n - fibNums.size();
			System.out.println("Iterating " + numIterations + " times.");

			for (int i = 1; i <= numIterations; i++){
				System.out.println("Adding " + prevNum + " and " + prevPrevNum);
				fibNums.add(prevNum + prevPrevNum);

				prevNum = fibNums.get(fibNums.size() - 1);
				prevPrevNum = fibNums.get(fibNums.size() - 2);
			}

			return fibNums.get(fibNums.size() - 1);
		}
		else{
			System.out.println("No need to recalculate - retrieving a previously cached value");
			return fibNums.get(n-1);
		}

	}//getFibNum()

	public static void main(String[] args){
		GitFibonacci fibonacci = new GitFibonacci();

		int n = 6;
		int number = fibonacci.getFibNum(n);
		System.out.println("Fibonacci number for n = " + n + " is " + number);

		n = 3;
		number = fibonacci.getFibNum(n);
		System.out.println("Fibonacci number for n = " + n + " is " + number);

		n = 5;
		number = fibonacci.getFibNum(n);
		System.out.println("Fibonacci number for n = " + n + " is " + number);

		n = 15;
		number = fibonacci.getFibNum(n);
		System.out.println("Fibonacci number for n = " + n + " is " + number);

	}

}