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.
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: