Pfthb

How many times is the fib method in invoked for fib(6).
where the fib method is

public static long fib(long index) 
 if (index == 0) // Base case
 return 0;
 else if (index == 1) // Base case
 return 1;
 else // Reduction and recursive calls
 return fib(index - 1) + fib(index - 2);
 
}

I end up tracing the recursive call to find how many times this method was called but this is so unpractical. Does this have a closed form function where you replace the value tested to know how many recursive call you will get?

Note that this was a question in my previous exam, (Exam is written) I know I could have used a count variable. Sorry for not mentioning this in the first place. This why am asking if there is a close form function for it.

You can pass some kind of Counter as an additional parameter that gets increased every time the function gets called:

class Counter 
 private int value = 0;
 public void increment() 
 value++;
 

 public int getCurrentValue() 
 return value;
 

So that your code will become:

public static long fib(long index, Counter counter) 
 counter.increment();
 if (index == 0) // Base case
 return 0;
 else if (index == 1) // Base case
 return 1;
 else // Reduction and recursive calls
 return fib(index - 1, counter) + fib(index - 2, counter);
 
}

The invocation:

Counter counter = new Counter();
fib(6,counter);
counter.getCurrentValue(); // retrieve the current value which is exactly the number of invocation of fib function

One option might be to add a static counter to your containing class:

public class YourFib 
 private static int counter;

 public static long fib(long index) 
 ++counter;
 if (index == 0) // Base case
 return 0;
 else if (index == 1) // Base case
 return 1;
 else // Reduction and recursive calls
 return fib(index - 1) + fib(index - 2);
 

 public static void main(String args) 
 counter = 0;
 fib(6l);
 System.out.println("There were " + counter + " recursive calls.");
 

By the way, computing the Fibonacci sequence using recursion is seriously sub-optimal. You should read about the dynamic programming say of doing this, where each level only needs to be computed once.

You can use something like this,

public class A 
 private static int count = 0;

 public static void main(String argv) 

 System.out.println(fib(6));
 System.out.println(count);
 

 public static long fib(long index) 
 count++;
 if (index == 0) // Base case
 return 0;
 else if (index == 1) // Base case
 return 1;
 else // Reduction and recursive calls
 return fib(index - 1) + fib(index - 2);
 

Create a integer variable in your main function, public static int count = 0;. Then but this variable into your recursive function shown as below:

`public static long fib(long index) 
 count ++;
 if (index == 0) // Base case
 return 0;
 else if (index == 1) // Base case
 return 1;
 else // Reduction and recursive calls
 return fib(index - 1) + fib(index - 2);`