CODEWITHSUNDEEP
javarecursion
Pit998
Pit998

Reputation: 49

Number of recursive calls

How to change the algorithm to further show the amount 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));
    }
}

Upvotes: 5

Views: 2403

Answers (4)

Beryllium
Beryllium

Reputation: 12988

I suggest separate classes for both counter 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 like this

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)");
    }
}

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

Upvotes: 2

Maroun
Maroun

Reputation: 95948

Static variables are initialized only once, so you can make a static counter variable, increment 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
    }
}

Upvotes: 0

Daniel Fischer
Daniel Fischer

Reputation: 183858

If you don't want to use a static counter, you can add a parameter for the counter. You need to wrap the counter into an object, so that it can be modified in a way 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.");
    }
}

Upvotes: 2

Rohan
Rohan

Reputation: 3078

You can use static variable to keep count of recursive call.

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);
    }
}

Upvotes: 4

Related Questions