Question

Create a class called FibGenerator with 3 methods:

1. public int nthFib(int n). This method should call computeFibRecurse(n).
2. private int computeFibRecurse(int n), which should recurse (that is, call itself) unless n is 1 or 2. If n is 1 or 2, the method should return 1.
3. A main method that prints “STARTING”, then constructs a FibGenerator generator and then calls nthFib(), passing in interesting values.

To look into this problem, you’re going to use software to analyze software. Add an instance variable: private int[] callCounter. In nthFib(n), initialize callCounter so that its length is n+1. In computeFibRecurse(n), increment callCounter[n]. Add a printCallCounter() method that prints like this:

0 calls to fib(0)

2584 calls to fib(1)

4181 calls to fib(2)

2584 calls to fib(3)

1597 calls to fib(4)

How would I frame this argument? My current code is:

package lab5workspace;

public class FibGenerator {

public int nthFib(int n) {

return computeFibRecurse(n);

}

private int computeFibRecurse(int n) {

if (n==1 || n== 2) {

return 1;

}

private int callCounter(int x) {

callCounter(x+1);

}

int result = computeFibRecurse(n-1) + computeFibRecurse(n-2);

System.out.println("The value is " + result);

return result;

}

public static void main(String[]args) {

System.out.println("starting");

FibGenerator fg = new FibGenerator();

int result = fg.nthFib(20);

}

}

Answer 1

FibGenerator.java

public class FibGenerator {

    private int[] callCounter;

    private int computeFibRecurse(int n) {
        callCounter[n]++;
        if (n == 1 || n == 2) {
            return 1;
        }
        return computeFibRecurse(n - 1) + computeFibRecurse(n - 2);
    }

    private void printCallCounter() {
        for (int i = 0; i < callCounter.length; i++) {
            System.out.println(callCounter[i] + " calls to fib(" + i + ")");
        }
    }

    public int nthFib(int n) {
        callCounter = new int[n + 1];
        int nfib = computeFibRecurse(n);
        printCallCounter();
        return nfib;
    }

    public static void main(String[] args) {
        System.out.println("STARTING");
        FibGenerator fg = new FibGenerator();
        int result = fg.nthFib(20);
    }
}

Output:

STARTING
0 calls to fib(0)
2584 calls to fib(1)
4181 calls to fib(2)
2584 calls to fib(3)
1597 calls to fib(4)
987 calls to fib(5)
610 calls to fib(6)
377 calls to fib(7)
233 calls to fib(8)
144 calls to fib(9)
89 calls to fib(10)
55 calls to fib(11)
34 calls to fib(12)
21 calls to fib(13)
13 calls to fib(14)
8 calls to fib(15)
5 calls to fib(16)
3 calls to fib(17)
2 calls to fib(18)
1 calls to fib(19)
1 calls to fib(20)

Process finished with exit code 0