5

如何更改算法以进一步显示递归调用的数量？

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

4 回答 4

4

您可以使用静态变量来保持递归调用的计数。

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);
    }
}
于 2013-05-25T08:53:20.110 回答
2

我建议为 counter 和 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;
    }
}

像这样使用

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

所以没有静态，每个参数/类都清楚地描述了它的用途。我更喜欢这个，因为它更具表现力，即使这个版本是最长的版本（由于附加类的样板）。

于 2013-05-25T22:14:46.813 回答
2

如果不想使用静态计数器，可以为计数器添加参数。您需要将计数器包装到一个对象中，以便可以以调用者可见的方式对其进行修改，例如长度为 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.");
    }
}
于 2013-05-25T08:54:03.163 回答
0

静态变量仅初始化一次，因此您可以创建一个静态计数器变量，在递归的第一行将其递增 1：

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
    }
}
于 2013-05-25T08:49:04.580 回答