Number of recursive calls

Question

How to change the algorithm to further display the number of recursive calls?

public class fibb { static long fibonacci(long n){ if (n == 0) return 0; else if (n == 1) return 1; else return fibonacci(n - 1) + fibonacci(n - 2); } public static void main(String[] args){ System.out.println(fibonacci(14)); } } 

Answer 1

If you do not want to use a static counter, you can add a parameter to the counter. You need to wrap the counter in an object so that it can be changed as visible to the caller, for example, an array of length 1:

 public class fibb { static long fibonacci(long n) { return fibonacci(n, null); } static long fibonacci(long n, long[] counter){ if (counter != null && counter.length > 0) ++counter[0]; if (n == 0) return 0; else if (n == 1) return 1; else return fibonacci(n - 1, counter) + fibonacci(n - 2, counter); } public static void main(String[] args){ long n = args.length > 0 ? Long.parseLong(args[0]) : 14; long[] counter = new long[1]; System.out.println(fibonacci(n, counter)); System.out.println(counter[0] + " calls to fibonacci."); } } 

Answer 2

You can use a static variable to save the recursive call count.

 public class fibb { public static int count; static long fibonacci(long n){ count++; if (n == 0) return 0; else if (n == 1) return 1; else return fibonacci(n - 1) + fibonacci(n - 2); } public static void main(String[] args){ System.out.println(fibonacci(14)); System.out.println("Number of times fibonacci function called is :" +count); } } 

Answer 3

I suggest separate classes for both counters and the result:

 class Counter { private int value = 0; public void inc() { value++; } public int get() { return value; } } class Result { public final long value; public final int calls; public Result(long value, int calls) { super(); this.value = value; this.calls = calls; } public final long getValue() { return this.value; } public final int getCalls() { return this.calls; } } 

to be used in this way

 public class FibonacciWithCounter { static Result fibonacci(long n) { final Counter counter = new Counter(); final long value = fibonacci(n, counter); return new Result(value, counter.get()); } static long fibonacci(long n, Counter counter) { counter.inc(); if (n == 0) return n; else if (n == 1) return n; else return fibonacci(n - 1, counter) + fibonacci(n - 2, counter); } public static void main(String[] args) { final Result result = fibonacci(14); System.out.println("Result is " + result.value + " (" + result.getCalls() + " calls)"); } } 

Thus, there is no static, and each parameter / class clearly describes its purpose. I prefer this because it is more expressive, even if this version is the longest (due to the boiler plate of additional classes).

Answer 4

Static variables are initialized only once , so you can make a static counter variable, increase it by 1 in the first line of the recursion:

 public class fibb { private static int numberOfCalls = 0; static long fibonacci(long n){ numberOfCalls++; if (n == 0) return 0; else if (n == 1) return 1; else return fibonacci(n - 1) + fibonacci(n - 2); } public static void main(String[] args){ System.out.println(fibonacci(14)); //numberOfCalls is the number of the calls to the recursion } }