Fibonacci with 3 different recursion methods

Question

I'm trying to understand recursion with Java better and I'm doing a program which ist using iteration, head and tail recursion.It should count how many times does the different methods called. What should I add to the head and to the tail part to complete the program? Thank you in advance

public class Recursion {
    public static void main(String[] args) {
        System.out.println("Test fibonacci: 0 = 0");
        System.out.println("iterativ: " + fibIt(0));
        System.out.println("head: " + fibHr(0));
        System.out.println("tail: " + fibTr(0));

        System.out.println("\nTest fibonacci: 5 = 5");
        System.out.println("iterativ: " + fibIt(5));
        System.out.println("head: " + fibHr(5));
        System.out.println("tail: " + fibTr(5));

        System.out.println("\nTest fibonacci: 10 = 55");
        System.out.println("iterativ: " + fibIt(10));
        System.out.println("head: " + fibHr(10));
        System.out.println("tail: " + fibTr(10));
    }

    private static int fibIt(int n) {
        switch (n) {
            case 0:
                return 0;
            case 1:
                return 1;
        }

        int a = 0;
        int b = 1;

        for (int i = 2; i <= n; i++) {
            b = a + b;
            a = b - a;
        }

        return b;
    }

    private static int fibHr(int n) {
        int counter = 0;
        switch (n) {
            case 0:
                counter +=1;
                return 0; 
            case 1:
                counter += 1;
                return 1;
            default:
                counter = counter +1;
                return fibHr(n - 1) + fibHr(n - 2) ;    
        }
    }

    private static int fibTr(int n) {
        return fibTr(0, 1, n);
    }

    private static int fibTr(int a, int b, int n) {
        switch (n) {
            case 0:
                return a;
            case 1:
                return b;
            default:
                return fibTr(b, a + b, n - 1);
        }
    }    
}

How can I get the counter value in the head recursion? I have tried everything to print it out but I have no clue how does it work. I would like to count the number of returns I have tried System.out.print but I simply got a huge number of 1-s.

Answer 1

You can convert each method to an instance method of a class which then holds the counter in a private field, with a getter to expose the value.

public class HeadRecursion {
  private long counter = 0;
  public int fib(int n) {
    ++counter;
    switch (n) {
        case 0:
            return 0;
        case 1:
            return 1;
        default:
            return fibHr(n - 1) + fibHr(n - 2);
    }
  }
  public long getCounter() { return count; }
}

Then you can instantiate your class, run your function and then get and output the counter:

public static void main() {
  final var obj = new HeadRecursion();
  final var number = obj.fib(10);
  System.out.println(number);
  System.out.println(obj.getCounter());
}

Note that the counter must be a field declared in the class and not a local variable defined inside the method due to at least two reasons:

• A local variable is not visible nor accessible outside its scope, i.e. the enclosing function
• Every time the function is called, the variable would be re-initialized. Each recursive call would start with the original value of the variable again.