/*
 * Creator: Nighthawk Coding Society
 * Mini Lab Name: fibonaccinacci sequence, featuring a Stream Algorithm
 * 
 */

import java.util.ArrayList;  
import java.util.HashMap;
import java.util.stream.Stream;

/* Objective will require changing to abstract class with one or more abstract methods below */
abstract class fibonacci {
    String name;  // name or title of method , no name is set
    int size;  // nth sequence
    int hashID;  // counter for hashIDs in hash map
    ArrayList<Long> list;   // captures current fibonaccinacci sequence
    HashMap<Integer, Object> hash;  // captures each sequence leading to final result

    int first = 1;
    int second = 1;
    /*
     Zero parameter constructor uses Telescoping technique to allow setting of the required value nth
     @param: none
     */
    public fibonacci() {
        this(20); // telescope to avoid code duplication, using default as 20
    }

    /*
     Construct the nth fibonaccinacci number
     @param: nth number, the value is constrained to 92 because of overflow in a long
     */
    public fibonacci(int nth) {
        this.size = nth;
        this.list = new ArrayList<>();
        this.hashID = 0;
        this.hash = new HashMap<>();
        //initialize fibonaccinacci and time mvc
        this.init();
    }

    /*
     This Method should be "abstract"
        */
    protected abstract void init();


    /*
     Number is added to fibonaccinacci sequence, current state of "list" is added to hash for hashID "num"
     */
    public void setData(long num) { // the number in setdata is added here
        list.add(num); // the number is added to the list
        hash.put(this.hashID++, list.clone()); // the hash id is incremented and added as a key and list is added as a value in the hashmap
    }

    /*
     Custom Getter to return last element in fibonaccinacci sequence
     */
    public long getNth() {
        return list.get(this.size - 1);
    }

    /*
     Custom Getter to return last fibonaccinacci sequence in HashMap
     */
    public Object getNthSeq(int i) {
        return hash.get(i);
    }

    /*
     Console/Terminal supported print method
     */
    public void print() {
        System.out.println("Init method = " + this.name);
        System.out.println("fibonaccinacci Number " + this.size + " = " + this.getNth());
        System.out.println("fibonaccinacci List = " + this.list);
        System.out.println("fibonaccinacci Hashmap = " + this.hash);
        for (int i=0 ; i<this.size; i++ ) {
            System.out.println("fibonaccinacci Sequence " + (i+1) + " = " + this.getNthSeq(i));
        }
    }

    
}
public class fibonacciFor extends fibonacci{
    

    @Override
    public void init() {
        this.name = "For Loop"; // setting name

        this.setData(0); // first item in the list
        this.setData(first);
        this.setData(second);
        int loopSize = this.size - 3;
        for(int i = 0;i<loopSize;i++) {
            int next = second;
            second = second + first;
            first = next;
            this.setData(second);
        }
    }
    
    static public void main(String[] args) {
        fibonacciFor fib = new fibonacciFor();
        fib.print();
    }
}
fibonacciFor.main(null);
Init method = For Loop
fibonaccinacci Number 20 = 4181
fibonaccinacci List = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]
fibonaccinacci Hashmap = {0=[0], 1=[0, 1], 2=[0, 1, 1], 3=[0, 1, 1, 2], 4=[0, 1, 1, 2, 3], 5=[0, 1, 1, 2, 3, 5], 6=[0, 1, 1, 2, 3, 5, 8], 7=[0, 1, 1, 2, 3, 5, 8, 13], 8=[0, 1, 1, 2, 3, 5, 8, 13, 21], 9=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34], 10=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55], 11=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89], 12=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144], 13=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233], 14=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377], 15=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610], 16=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987], 17=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597], 18=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584], 19=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]}
fibonaccinacci Sequence 1 = [0]
fibonaccinacci Sequence 2 = [0, 1]
fibonaccinacci Sequence 3 = [0, 1, 1]
fibonaccinacci Sequence 4 = [0, 1, 1, 2]
fibonaccinacci Sequence 5 = [0, 1, 1, 2, 3]
fibonaccinacci Sequence 6 = [0, 1, 1, 2, 3, 5]
fibonaccinacci Sequence 7 = [0, 1, 1, 2, 3, 5, 8]
fibonaccinacci Sequence 8 = [0, 1, 1, 2, 3, 5, 8, 13]
fibonaccinacci Sequence 9 = [0, 1, 1, 2, 3, 5, 8, 13, 21]
fibonaccinacci Sequence 10 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
fibonaccinacci Sequence 11 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
fibonaccinacci Sequence 12 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
fibonaccinacci Sequence 13 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]
fibonaccinacci Sequence 14 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233]
fibonaccinacci Sequence 15 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
fibonaccinacci Sequence 16 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]
fibonaccinacci Sequence 17 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987]
fibonaccinacci Sequence 18 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597]
fibonaccinacci Sequence 19 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584]
fibonaccinacci Sequence 20 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]
public class whileloop extends fibonacci{
    

    @Override
    public void init() {
        this.name = "While Loop";
        this.setData(0);
        this.setData(first);
        this.setData(second);
        int loopSize = this.size - 3;
        int i = 0;
        while(i < loopSize) {
            int temp = second;
            second = second + first;
            first = temp;
            this.setData(second);
            i++;
        }
    }
    
    static public void main(String[] args) {
        whileloop fib = new whileloop();
        fib.print();
    }
}
whileloop.main(null);
Init method = While Loop
fibonaccinacci Number 20 = 4181
fibonaccinacci List = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]
fibonaccinacci Hashmap = {0=[0], 1=[0, 1], 2=[0, 1, 1], 3=[0, 1, 1, 2], 4=[0, 1, 1, 2, 3], 5=[0, 1, 1, 2, 3, 5], 6=[0, 1, 1, 2, 3, 5, 8], 7=[0, 1, 1, 2, 3, 5, 8, 13], 8=[0, 1, 1, 2, 3, 5, 8, 13, 21], 9=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34], 10=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55], 11=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89], 12=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144], 13=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233], 14=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377], 15=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610], 16=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987], 17=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597], 18=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584], 19=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]}
fibonaccinacci Sequence 1 = [0]
fibonaccinacci Sequence 2 = [0, 1]
fibonaccinacci Sequence 3 = [0, 1, 1]
fibonaccinacci Sequence 4 = [0, 1, 1, 2]
fibonaccinacci Sequence 5 = [0, 1, 1, 2, 3]
fibonaccinacci Sequence 6 = [0, 1, 1, 2, 3, 5]
fibonaccinacci Sequence 7 = [0, 1, 1, 2, 3, 5, 8]
fibonaccinacci Sequence 8 = [0, 1, 1, 2, 3, 5, 8, 13]
fibonaccinacci Sequence 9 = [0, 1, 1, 2, 3, 5, 8, 13, 21]
fibonaccinacci Sequence 10 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
fibonaccinacci Sequence 11 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
fibonaccinacci Sequence 12 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
fibonaccinacci Sequence 13 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]
fibonaccinacci Sequence 14 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233]
fibonaccinacci Sequence 15 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
fibonaccinacci Sequence 16 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]
fibonaccinacci Sequence 17 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987]
fibonaccinacci Sequence 18 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597]
fibonaccinacci Sequence 19 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584]
fibonaccinacci Sequence 20 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]
public class fibonacciRecur extends fibonacci{

    @Override
    public void init() {
        this.name = "Recursion";
        for (int i=0; i<this.size; i++){
            this.setData(recursiveFib(i));
        }
    }
    
    // Recursion method
    public int recursiveFib(int n) {
        if (n == 0) {
            return 0;
        } else 
        if (n == 1) {
            return this.first;
        } else if (n == 2) {
            return this.second;
        } 
        return recursiveFib(n-2) + recursiveFib(n-1);

    }
    static public void main(String[] args) {
        fibonacciRecur fib = new fibonacciRecur();
        fib.print();
    }
}
fibonacciRecur.main(null);
Init method = Recursion
fibonaccinacci Number 20 = 4181
fibonaccinacci List = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]
fibonaccinacci Hashmap = {0=[0], 1=[0, 1], 2=[0, 1, 1], 3=[0, 1, 1, 2], 4=[0, 1, 1, 2, 3], 5=[0, 1, 1, 2, 3, 5], 6=[0, 1, 1, 2, 3, 5, 8], 7=[0, 1, 1, 2, 3, 5, 8, 13], 8=[0, 1, 1, 2, 3, 5, 8, 13, 21], 9=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34], 10=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55], 11=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89], 12=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144], 13=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233], 14=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377], 15=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610], 16=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987], 17=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597], 18=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584], 19=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]}
fibonaccinacci Sequence 1 = [0]
fibonaccinacci Sequence 2 = [0, 1]
fibonaccinacci Sequence 3 = [0, 1, 1]
fibonaccinacci Sequence 4 = [0, 1, 1, 2]
fibonaccinacci Sequence 5 = [0, 1, 1, 2, 3]
fibonaccinacci Sequence 6 = [0, 1, 1, 2, 3, 5]
fibonaccinacci Sequence 7 = [0, 1, 1, 2, 3, 5, 8]
fibonaccinacci Sequence 8 = [0, 1, 1, 2, 3, 5, 8, 13]
fibonaccinacci Sequence 9 = [0, 1, 1, 2, 3, 5, 8, 13, 21]
fibonaccinacci Sequence 10 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
fibonaccinacci Sequence 11 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
fibonaccinacci Sequence 12 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
fibonaccinacci Sequence 13 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]
fibonaccinacci Sequence 14 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233]
fibonaccinacci Sequence 15 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
fibonaccinacci Sequence 16 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]
fibonaccinacci Sequence 17 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987]
fibonaccinacci Sequence 18 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597]
fibonaccinacci Sequence 19 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584]
fibonaccinacci Sequence 20 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]

Collegeboard Standards

1.B

Implementing a while loop, for loop, and recursive function to accomplish fibonacci.

4.C

All 3 algorithms returned the same result through the printed output being the same.

5.A

For and while loops run in linear time since they run through the input size once and do a constant amount of operations for each loop. The recursive algorithm takes exponential time, however, since for each term of the sequence, the algorithm needs to recalculate all of the other terms as well due to the nature of recursion.